A probability-based unified framework for semantic search and recommendation

Abstract

The objective of search and recommendation is to provide users with documents that are relevant to their needs. Keyword-based search and recommendation approaches suffer from sparsity and semantic ambiguity problems because they correlate users’ needs with documents only via keywords. Thus, for a given query, some documents that are semantically relevant to a user’s needs are not provided if they do not include specific keywords. To address this, some search approaches have used the authority of documents, which is commonly represented using hyperlinks within documents. However, if there are no hyperlinks, it is difficult to exploit the authority for ranking documents. As the links of documents are determined by their owners, the authority derived from links does not consider users’ current needs. In order to resolve these problems, we propose a unified framework for semantic search and recommendation to enrich the semantics of users’ needs and documents with their corresponding concepts and to use personalized authority derived from recommendation approaches. The proposed approach makes it possible to retrieve documents with a high degree of semantic relevance as well as high authority. Through extensive experiments, we show that our approach outperforms conventional search and recommendation approaches.

Keywords

collaborative filtering information retrieval personalization probability recommendation semantic search web search

1. Introduction

As the acquisition of documents relevant to users’ needs has become a critical issue, many studies have proposed their own approaches in terms of two aspects: ‘search’ and ‘recommendation’ [1]. Search approaches are to accept queries from users and return relevant documents. Most search approaches exploit exact matching of keywords derived from queries and documents; this approach is referred to as keyword search. In general, the quality of search results in keyword search depends upon the quality of user-specified inputs such as queries. If users are unaccustomed to expressing their needs with precise queries, it may be difficult for keyword search to provide appropriate documents. To complement keyword search, various recommendation approaches have been proposed which are to find documents that conform to users’ preferences (instead of queries) and predict rating scores for documents based on users’ preferences [2].

Owing to their simplicity and efficiency, keywords are widely used in many search and recommendation approaches [3]. However, keyword-based approaches have three problems: sparsity, semantic ambiguity and non-personalized authority. First, as the number of keywords in database increases, the density of documents with respect to the given keywords decreases [4]. For example, for a query, some documents that do not include keywords derived from users’ needs (i.e. queries or preferences) cannot be provided to users even though the documents are semantically relevant to a given user’s needs; this is referred to as the sparsity problem. Second, although documents include the keywords derived from users’ needs, they may not be precisely relevant to a given user’s needs. This is because a keyword can be interpreted in different ways (referred to as a homonym), or different keywords can mean the same thing (referred to as a synonym); this is referred to as the semantic ambiguity problem. To overcome the sparsity and semantic ambiguity problems, some studies have exploited the authority of documents as well as keyword-based relevance [5]. For example, if some candidate documents have the same degree of relevance to a given user’s needs, a document with high authority is top-ranked for the needs. Hyperlinks within documents have been widely used to represent the authority of documents; that is, documents that are frequently referenced (or hyperlinked) by others have high authority. This approach has been validated by the success of Google (http://www.google.com). However, if there are no hyperlinks, it is difficult to derive the authority of documents. Moreover, as the hyperlinks within documents are determined by their owner, the authority derived from the hyperlinks does not consider an active user’s current needs.¹ This means that search approaches using the authority derived from hyperlinks of documents cannot provide users with personalized results; this is referred to here as the non-personalized authority problem.

In order to resolve these problems, we propose a unified framework for semantic search and recommendation. The unified framework utilizes the enriched semantics of active users’ needs and documents. As humans interpret the semantics of specific entities with their domain knowledge, search and recommendation systems also require vast amounts of domain knowledge to understand the semantics of entities [6]. In the proposed framework, the active users’ needs and documents are represented by a set of concepts (derived from domain knowledge) as well as keywords to represent their semantics.

The unified framework offers three improvements over previous methods, summarized as follows:

By using enriched semantics, which are represented by a set of keywords and concepts, sparsity and semantic ambiguity problems are resolved. These problems cannot be avoided in keyword-based approaches because using keywords only cannot represent the semantics of active users’ needs and documents completely. The proposed unified framework complements the semantics of the users’ needs and documents with the concepts of domain knowledge.

The quality of search results can be improved by using personalized authority. As addressed previously, the authority derived from the hyperlinks of documents does not consider active users’ current needs. To resolve the non-personalized authority problem, we exploit the authority derived from recommendation approaches. Thus, the documents that an active user prefers will have higher authority than those that he/she does not prefer.

The proposed framework can decide an appropriate search and recommendation approach according to users’ circumstances. For example, users may be accustomed to expressing their needs with queries in some domains, but not others. Search approaches may be appropriate in the former case, and recommendation approaches may be appropriate in the latter.

To the best of our knowledge, few studies have proposed a unified framework for semantic search and recommendation, utilizing the implicit authority² of documents. The remainder of this paper is organized as follows. Section 2 represents a review of previous studies related to semantic search and recommendation. Section 3 describes a unified framework for semantic search and recommendation. Section 4 explains the detailed modelling for entities and their relationships in the proposed framework. Section 5 explains the derivatives in the framework and their probabilistic ranking functions. Section 6 shows the superiority of our approach via various experiments. Section 7 concludes this paper and discusses future work.

2. Related work

In this section, we briefly present some of the previous studies related to semantic search and recommendation.

2.1. Semantic search

Keyword search basically assumes that the inherent semantics of queries and documents are expressed by a few keywords. However, owing to sparsity and semantic ambiguity problems, most documents retrieved in response to queries are irrelevant to users’ needs. Consequently, some approaches analyse the hidden semantics of queries and documents; they are referred to as semantic search. In this work, we classify the semantic search approaches into three categories: logic-based, link-based and concept-based semantic search.

Logic-based semantic search [7, 8] utilizes a domain ontology that defines concepts and their relationships in the domain. As users’ needs can be described precisely with a specific query language (e.g. SPARQL and OWL-QL), semantic ambiguity is not considered a significant problem in logic-based semantic search. However, for ordinary users, acquiring the specific query language is considered a barrier. Furthermore, logic-based semantic search requires an inference engine to manage the given ontology. However, no inference engines are available to manage large ontologies within a reasonable period of time [9].

Link-based semantic search [10 –12] tries to find documents that are semantically relevant to active users’ queries through hyperlinks between documents. Link-based semantic search consists of two steps. First, initial documents that contain keywords in the given query are located based on exact matching between the query and documents. Then, semantically relevant documents that are frequently referenced by the initial documents are identified. Link-based semantic search can provide documents that are relevant to the given query even though they do not contain any keywords derived from the query. However, there are two limitations. First, because the first step is based on exact matching, there are still sparsity and semantic ambiguity problems. Second, if the hyperlinks of documents do not exist explicitly, the results are identical to those of keyword search.

Concept-based semantic search [3, 13 –15] represents the semantics of documents and users’ queries with concepts. The concepts can be explicitly selected by users or implicitly derived from users’ logs. The definitions of concepts are different depending on the domains (or applications). For example, Lee et al. [13] considered Web categories to be concepts, whereas Xu et al. [3] considered tags to be concepts. However, in general, concepts are assumed to be derived from domain knowledge (e.g. taxonomic knowledge, folksonomy). As users’ queries are correlated with documents via concepts in concept-based semantic search, the problems associated with keyword search (such as sparsity and semantic ambiguity) are resolved to some extent. By representing the user’s query and documents with their corresponding concepts, it is possible to retrieve documents that are semantically relevant to the given query even though the documents do not have any keywords of the query. Furthermore, the semantic ambiguity of keywords can be resolved because the conceptual representation for a given query can play a role in semantically disambiguating the query. Since recent studies on semantic search have focused on improving the quality of concept-based approaches, we refer to concept-based semantic search as ‘semantic search’, hereafter.

2.2. Recommendation

Recommendation can be classified into content-based filtering (CBF) and collaborative filtering (CF) [5]. CBF attempts to find documents similar to those liked by an active user in the past. As CBF has its root in keyword search and adopts many techniques of keyword search, the details of CBF are not discussed further in this paper.

The most successful and popular recommendation systems used in commercial sites are based on CF. CF identifies like-minded users whose preferences are similar to those of the active user. Then, CF recommends documents that those like-minded users prefer. As the techniques used in CF are different from those in search and CBF, the rest of this section reviews the derivatives of CF in detail. Although there are many criteria for classifying CF approaches, they are often classified into user-based collaborative filtering (UCF) and item-based collaborative filtering (ICF) [16, 17].

UCF [18 –20] has critical limitations such as a lack of scalability and real-time performance problems; that is, as the computational complexity increases linearly with the number of users, it is difficult to find like-minded users in real time [16]. ICF [21, 22] has been proposed to overcome these limitations. It predicts an active user’s preference for documents based on the degree of relevance between documents, rather than the degree of relevance between users. However, according to Mild and Natter [23], the recommendation quality of UCF is better than that of ICF. This work only considers UCF because our goal is to provide users with more reliable documents.

Despite their success and popularity, UCF and ICF have a critical drawback, which is the sparsity problem. When semantically like-minded users access different documents, it is difficult to determine whether those users have similar preferences. Our work focuses on solving the sparsity problem by associating users’ preferences and documents with their corresponding concepts. The sparsity problem cannot be avoided in CF using similarity measures such as Pearson’s correlation coefficient and cosine similarity [17, 18, 24, 25] because CF exploits exact matching of documents to estimate the degree of relevance between users who accessed those documents.

Several approaches have been proposed to alleviate sparsity problems. Dimensionality reduction [26, 27], which is based on matrix factorization, removes unrepresentative users or documents in order to reduce the dimensionalities of the user-item matrix. However, when certain users or documents are discarded through dimensionality reduction techniques, some useful data for recommendation may be lost and thus degrade the quality of recommendation [28]. In contrast, our approach solves the sparsity problem by increasing the semantic information for users and documents without losing any information. Hybrid approaches combining CBF and CF have been proposed to address this problem [29, 30]. In hybrid approaches, users’ preferences are represented by keywords extracted from documents, whereas in the proposed framework the preferences are represented by a set of concepts extracted from domain knowledge. As a result, it is possible to estimate the degree of semantic relevance between users who accessed different documents. Finally, clustering-based CF approaches [31, 32] recommend documents within a set of small clusters. However, these approaches have expensive clustering costs, and the quality of recommendation is generally low [28].

Recently, Zanardi and Capra [33] and Kim et al. [34] have proposed tagging-based CF approaches to alleviate the sparsity problem. The degree of relevance between an active user and like-minded users is derived by tags annotated by the users. If we regard the tags as concepts for computing similarity between users, the ideas are similar to our approach. However, if an active user does not provide any explicit feedback (e.g. tags), for reasons such as annoyance or hesitation, it is difficult to estimate the degree of relevance between users. Therefore, it is necessary to study how to utilize users’ implicit feedback (e.g. click-through logs) instead of explicit feedback. Chong and David. [35] have proposed a collaborative topic regression model for recommendation, which is based on latent Dirichlet allocation (LDA) [36]. A topic modelling approach such as LDA discovers a set of concepts (or topics) from training set, whereas the proposed framework explicitly derives concepts from domain knowledge. Since the concept space in world knowledge is larger than the one in LDA, we can estimate more reliable degree of semantic relevance between users.

3. Unified framework for semantic search and recommendation

Conventional search and recommendation approaches only exploit a single entity type to represent the semantics of active users’ needs and documents. For example, keyword search only exploits keywords to represent the semantics of active users’ queries and documents, whereas CF exploits like-minded users to represent the semantics of active users’ preferences and documents. As a single entity type cannot represent the semantics of users’ needs and documents completely, it causes several problems, such as sparsity, semantic ambiguity and non-personalized authority of documents in conventional search and recommendation approaches. To enrich the semantics of users’ needs and documents, our work proposes a unified framework for semantic search and recommendation. Because the unified framework exploits heterogeneous entities and their relationships, it enriches the semantics of users’ needs and documents, thereby resolving the sparsity and semantic ambiguity problems.

The rest of this section explains in detail how to resolve the problems in the proposed framework. First, it is difficult to completely represent the semantics of documents and users’ needs with a few keywords. Even though previous semantic search approaches exploit concepts instead of keywords to reduce the sparsity problem, they still focus on the content-based semantics of documents and users’ needs. In our work, we further reduce the sparsity problem by exploiting various semantics derived from heterogeneous relationships. For example, if documents do not contain the concepts derived from users’ needs, they cannot be provided to users in semantic search; that is, semantic search only utilizes containing relationships between concepts and documents. However, in the proposed framework, the documents can be provided to users if the active user (or other like-minded users) frequently accessed the documents; that is, in the proposed framework, accessing relationships between users and documents are also utilized to reduce the sparsity problem.

Second, the semantic ambiguity problem can be easily resolved through concepts derived from domain knowledge. Suppose that an active user who wants Web documents only related to ‘fruits’ submits the query ‘apple’ to a keyword search system. The search system will provide the user with documents related to ‘computers’ as well as ‘fruits’. The documents related to ‘computers’ are irrelevant to the user’s current needs. Similar to the approach proposed by Wolfman [37], the given query ‘apple’ can be expanded with frequently co-occurring keywords in the user’s query log. However, if the expanded keywords cannot remove the semantic ambiguity of the given query, the results may still be irrelevant to the user’s needs. For example, if the expanded keyword is ‘price’, search results derived from ‘apple’ and ‘price’ may still be related to ‘computers’ as well as ‘fruits’. This is because the expanded keyword ‘price’ does not completely disambiguate the semantics of the given needs. By using keywords derived from concepts, it is possible to make the user’s needs obvious. A keyword (e.g. ‘fruit’) representing a concept is used as the expanded query.

Third, some keyword search engines such as Google (http://www.google.com) have shown that the authority of documents helps to provide more accurate results. Most studies of semantic search performed to date have not considered the authority of documents. Although link-based semantic search approaches consider the authority of documents, they are constrained to documents with hyperlinks such as Web documents. As addressed in Section 2.1, if the links of documents do not exist explicitly, it is difficult to derive the authority of documents. Furthermore, as the links of documents are determined by their owner (or creator), the authority derived from the links does not consider a user’s current needs. That is, search approaches using the authority derived from links of documents cannot provide users more personalized results. To derive the personalized authority of documents that do not have any explicit links, we utilize CF approaches. Links between like-minded users can be used to determine the authority of documents, which is referred to as implicit authority. Consequently, the documents that like-minded users prefer are assumed to have higher authority than those preferred by unlike-minded users. Hybrid approaches to semantic search and recommendation can provide users the documents that have a high degree of relevance as well as high authority.

Figure 1 shows four entity types (i.e. users, terms, documents, and concepts) and their relationships in the unified framework. In this work, users represent active users’ needs such as queries and preferences, and terms refer to compound words (or keywords) as well as to single words. An edge represents the many-to-many relationships between two entity types. For example, in Figure 1, a document is related to a set of concepts, and vice versa. Two entities are assumed to be semantically relevant if they are connected by direct or indirect edges. Direct edges are referred to as explicit relationships between two entities, whereas indirect edges are referred to as implicit relationships. The implicit relationships can be derived (or inferred) from explicit relationships. In Sections 3.1 and 4, we describe in detail how to model entities and their relationships.

3.1. Modelling of entities

This section describes the modelling of entities used in the unified framework. Section 3.1.1 explains how to model documents with term vectors. Sections 3.1.2 and 3.1.3 explain how to model users and concepts, respectively.

3.1.1. Documents

Similar to the vector space model [38] that is the most commonly used technique in information retrieval, we represent a document with a set of index terms which are formally described as follows:

Definition 1. Given a document space $D = {d_{1}, \dots, d_{i}, \dots, d_{| D |}}$ ,³ let D be a set of documents, and |D| be the total number of documents in the given space. Each document is described by |V| dimensional index terms, and V is the set of index terms. A weight w_i,k is associated with each index term t_k of a document $d_{i}$ , which is formally defined as follows:

d_{i} = 〈 w_{i, 1}, \dots, w_{i, k}, \dots, w_{i, | V |} 〉

Each term weight w_i,k is estimated by using the term frequency (TF) and inverse document frequency (IDF), and is normalized to remove the possibility that long documents have higher ranks than short documents.

When estimating term weights, stop words (e.g. articles, prepositions and conjunctions) are removed, and the Porter stemming algorithm [39] can be used to transform inflected words to their root forms.

3.1.2. Users

We assume that a user u can be replaced with a user’s needs such as a query (denoted as $u_{q}$ ) and preference (denoted as $u_{p}$ ); that is, we consider the modelling of users’ needs as the modelling of users. In general, a user’s needs are provided to a system explicitly or implicitly. If the proposed framework is used for a search system, user queries are explicitly given to the system. If the framework is used for a recommendation system, users’ preferences are explicitly or implicitly given to the system. As it is difficult to collect user’s explicit needs owing to privacy issues, many studies, including our approach, have focused on exploiting users’ implicit needs derived from their access logs. This section describes how to model users’ implicit needs.

Definition 2. Given a user space $U = {u_{1}, \dots, u_{i}, \dots, u_{| U |}}$ , let U be a set of users’ implicit needs, and |U| be the total number of users’ implicit needs in the given space. Suppose that a user with an implicit need $u_{j}$ has accessed n documents. Each user with an implicit need $u_{j}$ is defined as the average term vectors derived from n documents, which is formally defined as follows:

u_{j} = \frac{1}{| D^{u_{j}} |} \sum_{d_{n}^{u_{j}} \in D^{u_{j}}} d_{n}^{u_{j}}, where D^{u_{j}} = {d_{1}^{u_{j}}, \dots, d_{i}^{u_{j}}, \dots, d_{n}^{u_{j}}}

(1)

In equation (1), $D^{u_{j}}$ is the set of documents that a user with an implicit need $u_{j}$ accessed. A document $d_{i}^{u_{j}}$ is the ith document in $D^{u_{j}}$ , and is represented by a weighted term vector: that is, $d_{i}^{u_{j}} = 〈 w_{i, 1}, \dots, w_{i, k}, \dots, w_{i, | V |} 〉$ , where w_i,k is the weight of the kth term and V is the set of index terms. The derived terms vector for a user is normalized to remove the effect of length.

3.1.3. Concepts

According to the formal concept analysis theory [40], a set of entities that belongs to a concept can be used to approximate the semantics of the concept [41].

Definition 3. Given a concept space $C = {c_{1}, \dots, c_{x}, \dots, c_{| C |}}$ , let C be a set of concepts in a predefined domain knowledge, and |C| be the total number of concepts. As a concept is approximated by entities that belong to the concept, each concept $c_{x}$ is represented by the average of term vectors derived from the entities, which is formally defined as follows:

c_{x} = \frac{1}{| E^{c_{x}} |} \sum_{e_{j}^{c_{x}} \in E^{c_{x}}} e_{j}^{c_{x}}, where E^{c_{x}} = {e_{1}^{c_{x}}, \dots, e_{j}^{c_{x}}, \dots, e_{m}^{c_{x}}}

(2)

In equation (2), $E^{c_{x}}$ is the set of entities that belong to a concept $c_{x}$ . An entity ${e_{i}}^{c_{x}}$ is the jth entity in $E^{c_{x}}$ , and it is represented by a weighted term vector; that is, e_i^c_x $= 〈 w_{i, 1}, \dots, w_{i, k}, \dots, w_{i, | V |} 〉$ where w_i,k is the weight of the kth term and V is the set of index terms. The derived terms vector for a concept is normalized to remove the effect of length. In this work, we utilize the concepts extracted from domain knowledge. A practical approach to using domain knowledge is to exploit world knowledge⁴ such as a Web directory or encyclopaedia. The categories in a Web directory and the topics in an encyclopedia can be considered concepts. For example a category (e.g. http://www.dmoz.org/Arts/Music/Styles/J/Jazz) in the Open Directory Project Web directory (ODP) or a topic (e.g. http://en.wikipedia.org/wiki/Jazz) in Wikipedia is regarded as a concept, Jazz. Each category in ODP has several descriptions, whereas each topic in Wikipedia has a single description;⁵ in this paper, a description that belongs to a concept is considered an entity describing the semantics of the concept.

4. Modelling of relationships

We utilize a probabilistic approach to model relationships between entities because it provides a clear formalism [38]. That is, entities are represented by their random variables, and their relationships are expressed by conditional probabilities. In this work, we classify the relationships into two groups: explicit relationships and implicit relationships.

4.1. Explicit relationships

As addressed in Section 3, entities such as documents, users, and concepts are based on the relationships with terms (denoted as containing relationships in Figure 1). As containing relationships exist explicitly, they are regarded here as explicit relationships. First, the relationships between users and terms (user–term relationships) represent terms contained in users’ explicit needs (i.e. queries and preferences). This is formally defined as follows:

Pr (t_{k} | u) = {\begin{matrix} \frac{w (u, t_{k})}{\sum_{t_{j}} w (u, t_{j})} & if t_{k} \in u \\ 0 & otherwise \end{matrix}

(3)

In equation (3), $Pr (t_{k} | u)$ indicates the probability of observing a term $t_{k}$ , given that a user’s needs⁶ have been observed (or submitted). Moreover, the numerator of equation (3) denotes the weight of the kth term in a user’s needs, and the denominator denotes the total weight sum of all terms in a user’s needs. Second, the relationships between documents and terms (document–term relationships) as well as the relationships between concepts and terms (concept–term relationships) represent terms contained in documents and concepts, respectively. That is, document–term relationships can be estimated by equation (4).:

Pr (t_{k} | d_{i}) = {\begin{matrix} \frac{w (d_{i}, t_{k})}{\sum_{t_{j}} w (d_{i}, t_{j})} & if t_{k} \in d_{i} \\ 0 & otherwise \end{matrix}

(4)

In equation (4), the numerator $w (d_{i}, t_{k})$ denotes the weight of the kth term in a document $d_{i}$ , and the denominator $\sum_{t_{j}} w (d_{i}, t_{j})$ denotes the total weight sum of all terms in a document $d_{i}$ . Third, the concept–term relationship is estimated by equation (5).

Pr (t_{k} | c_{x}) = {\begin{matrix} \frac{w (c_{x}, t_{k})}{\sum_{t_{j}} w (c_{x}, t_{j})} & if t_{k} \in c_{x} \\ 0 & otherwise \end{matrix}

(5)

where the numerator denotes the weight of the kth term in $c_{x}$ , and the denominator denotes the total weight sum of all terms in $c_{x}$ . As documents and concepts consist of terms, document–term relationships as well as concept–term relationships are similarly estimated in this work.

Finally, there are additional explicit relationships, namely, accessing relationships between users and documents (user–document relationships). The relationships represent documents accessed by users. They can be derived by analysing the click-through counts, which can be defined as follows:

Pr (d_{i} | u) = \frac{access (u, d_{i})}{\sum_{d_{j}} access (u, d_{j})}

(6)

In equation (6), $Pr (d_{i} | u)$ is the probability of observing a document $d_{i}$ , given that a user with needs (i.e. $u_{q}$ or $u_{p}$ ) has been observed. The numerator $access (u, d_{i})$ is the access count of a user who has a need for a document $d_{i}$ , and the denominator $\sum_{d_{j}} access (u, d_{j})$ is the total access count of the user for all documents. The explicit relationships explained by equations (3)–(6) are denoted in Figure 2.

4.2. Implicit relationships

The estimation of implicit relationships between two entities can be inferred from explicit relationships with other entities that correlate two entities, which is formalized in Proposition 1.

Proposition 1. Let O be an entity set that correlates two entities $e_{i} \notin O$ and $e_{j} \notin O$ The probability, which represents an implicit relationship between two entities $e_{i}$ and $e_{j}$ , is proportional to the sum of products of probabilities that represent explicit relationships with entities in the entity set O. Consequently,

Pr (e_{i} | e_{j}) \propto Pr (e_{j} | e_{i}) \propto \sum_{\forall o_{r} \in O} Pr (o_{r} | e_{i}) \cdot Pr (o_{r} | e_{j})

(7)

Proof. By applying Bayes’ theorem to $Pr (e_{i} | e_{j})$ , the propositional relationships can be proved as follows:

Pr (e_{i} | e_{j}) = \frac{Pr (e_{i})}{Pr (e_{j})} \cdot Pr (e_{j} | e_{i})

The prior probabilities of each entity (i.e. $Pr (e_{i})$ and $Pr (e_{j})$ ) are assumed to be constant for their random variables. Consequently, the above equation can be rewritten as the following proportional equation:

Pr (e_{i} | e_{j}) \propto Pr (e_{j} | e_{i})

(8)

Furthermore, by applying the definition of conditional probability and the law of total probability, the probability $Pr (e_{i} | e_{j})$ can be defined as follows:

Pr (e_{i} | e_{j}) = \frac{Pr (e_{i} \cap e_{j})}{Pr (e_{j})} = \frac{1}{Pr (e_{j})} \cdot \sum_{\forall o_{r}} Pr (e_{i} \cap e_{j} | o_{r}) \cdot Pr (o_{r})

According to the principle of maximum entropy, the joint probability $Pr (e_{i} \cap e_{j} | o_{r})$ is equal to the product of $Pr (e_{i} | o_{r})$ and $Pr (e_{j} | o_{r})$ [42]. Thus, the above equation can be rewritten as follows:

\frac{1}{Pr (e_{j})} \cdot \sum_{\forall o_{r}} Pr (e_{i} | o_{r}) \cdot Pr (e_{j} | o_{r}) \cdot Pr (o_{r})

By applying Bayes’s theorem, the above equation can be rewritten as follows:

\frac{1}{Pr (e_{j})} \cdot \sum_{\forall o_{r}} {\frac{Pr (e_{i}) \cdot Pr (o_{r} | e_{i})}{Pr (o_{r})} \cdot \frac{Pr (e_{j}) \cdot Pr (o_{r} | e_{j})}{Pr (o_{r})} \cdot Pr (o_{r})} = \sum_{\forall o_{r}} \frac{Pr (e_{i})}{Pr (o_{r})} \cdot Pr (o_{r} | e_{i}) \cdot Pr (o_{r} | e_{j})

The prior probabilities of each entity (i.e. $Pr (e_{i})$ and $Pr (o_{r})$ ) are assumed to be constant for their random variables. Consequently, the above equation can be rewritten as the following proportional equation:

Pr (e_{i} | e_{j}) \propto \sum_{\forall o_{r} \in O} Pr (o_{r} | e_{i}) \cdot Pr (o_{r} | e_{j})

(9)

Finally, the following equation can be derived by combining equations (8) and (9).

Pr (e_{i} | e_{j}) \propto Pr (e_{j} | e_{i}) \propto \sum_{\forall o_{r} \in O} Pr (o_{r} | e_{i}) \cdot Pr (o_{r} | e_{j})

In Proposition 1, we assume that probabilities $Pr (o_{r} | e_{i})$ and $Pr (o_{r} | e_{j})$ represent the explicit relationships between entities. Thus, the probabilities $Pr (e_{i} | e_{j})$ and $Pr (e_{j} | e_{i})$ represent the implicit relationships between two entities $e_{i}$ and $e_{j}$ via entities O. By using Proposition 1, various types of implicit relationship can be easily defined from explicit relationships. First, using equation (9), a user–term relationship can be defined as follows:

Pr (t_{k} | u) \propto Pr (u | t_{k}) \propto \sum_{\forall d_{i}} Pr (d_{i} | u) \cdot Pr (d_{i} | t_{k})

(10)

The user–term relationship in equation (10) is the implicit relationship between a user’s needs and a term while user–term relationship in equation (3) is the explicit relationship between user’s needs and a term. The user–term relationship in equation (10) is derived from explicit relationships with documents. Second, the implicit relationship between a document and a concept (denoted as concept-document relationship) can be defined as follows:

Pr (d_{i} | c_{x}) \propto Pr (c_{x} | d_{i}) \propto \sum_{\forall t_{k}} Pr (t_{k} | d_{i}) \cdot Pr (t_{k} | c_{x})

(11)

As shown in equation (11), terms (i.e. $\forall t_{k}$ ) are used to correlate a document $d_{i}$ with a concept $c_{x}$ . Finally, the implicit relationship between a user and a concept (i.e. concept–user relationship) can be defined as follows:

Pr (u | c_{x}) \propto Pr (c_{x} | u) \propto \sum_{\forall d_{i}} Pr (d_{i} | u) \cdot Pr (d_{i} | c_{x})

(12)

As the relationships between documents and concepts are derived from the relationships with terms, equations (11) and (12) are combined. Consequently, equation (12) is rewritten as follows:

Pr (u | c_{x}) \propto \sum_{\forall d_{i}} Pr (d_{i} | u) \cdot {\sum_{\forall t_{k}} Pr (t_{k} | d_{i}) \cdot Pr (t_{k} | c_{x})}

(13)

In equation (13), documents (i.e. $\forall d_{i}$ ) and terms (i.e. $\forall t_{k}$ ) are used to correlate a user’s need with a concept. Here, $Pr (d_{i} | u)$ is the probability of observing a document $d_{i}$ given that a user’s need has been observed, which is defined in equation (6).

The implicit relationships explained by equations (10), (11) and (13) are denoted in Figure 3. In the figure, user–term relationships are derived from the relationships between users, documents, and terms ①, and concept–document relationships and concept–user relationships are derived from the relationships denoted by ② and ③, respectively.

5. Derivatives in the unified framework

Since the proposed framework is intended to unify search and recommendation approaches, it subsumes conventional search and recommendation approaches; that is, conventional approaches are considered special cases in the proposed framework. The following sections explain how to adapt conventional approaches to the proposed framework. In addition, we introduce their probabilistic ranking functions in detail.

5.1. Keyword search

In keyword search, documents containing keywords submitted by an active user are considered search results. As a result, terms are used to correlate a user (i.e. a user’s query) with documents. For example, suppose that a user submits a query (denoted as $u_{q}$ ), which contains a term $t_{k}$ . As a document $d_{i}$ contains the query term $t_{k}$ , the document $d_{i}$ is returned to the user, who has an information need (denoted as $u_{q}$ ), as a search result. This is illustrated in Figure 4(a). Most keyword search approaches utilize only explicit relationships between users, terms and documents (i.e. user–term relationships and document–term relationships), which are indicated by dotted lines in Figure 5(a). The rank of a document for a given query can be estimated with $\Pr_{k s} (d_{i} | u_{q})$ , and terms are used to correlate a user’s query with a document. By applying Proposition 1, the probability $\Pr_{k s} (d_{i} | u_{q})$ can be defined as follows:

\Pr_{k s} (d_{i} | u_{q}) \propto \sum_{\forall t_{k}} Pr (t_{k} | d_{i}) \cdot Pr (t_{k} | u_{q})

(14)

In equation (14), the conditional probabilities $Pr (t_{k} | d_{i})$ and $Pr (t_{k} | u_{q})$ represent the explicit relationships between a term, a document and a query. We assume that these explicit relationships can be estimated by equations (3) and (4).

5.2. Semantic search

Semantic search represents the semantics of documents and users’ queries with concepts (not keywords). As documents and concepts are represented by a set of terms, it is possible to estimate the degrees of relevance between documents and concepts (i.e. exploiting relating relationships as shown in Figure 4(b)). Similarly, a user’s query also consists of a set of terms. Therefore, it is possible to estimate the degrees of relevance between terms and concepts (i.e. exploiting containing relationships between terms and concepts as shown in Figure 5(b)).

Figure 5(b) represents user–term relationships, concept–term relationships and concept–document relationships that are used in semantic search. For example, suppose that a user submits a query that contains a term $t_{k}$ . As the concept $c_{x}$ contains the term $t_{k}$ , the user’s query $u_{q}$ is mapped to the concept $c_{x}$ . As the document $d_{i}$ is also represented by the concept $c_{x}$ , the degree of semantic relevance between the given query and document can be estimated via the concept $c_{x}$ . This is shown in Figure 4(b), and entity types such as terms and concepts are used to correlate a user’s query and a document (Figure 5(b)). Similar to keyword search, the rank of a document for a query is estimated by the probability Pr_SS(d_i|u_q|). Terms and concepts are used to correlate a user’s query with a document in semantic search, whereas only terms are used in keyword search. Thus, the probability Pr_SS(d_i|u_q|) is defined as follows:

\Pr_{S S} (d_{i} | u_{q}) \propto \sum_{\forall c_{x}} Pr (c_{x} | d_{i}) \cdot Pr (c_{x} | u_{q})

(15)

where the implicit relationships (i.e. $Pr (c_{x} | d_{i})$ and $Pr (c_{x} | u_{q})$ ) can be defined via terms, which were explained in equations (11) and (12). Consequently, equation (15) can be rewritten as follows:

\Pr_{S S} (d_{i} | u_{q}) \propto \sum_{\forall c_{x}} {(\sum_{\forall t_{k}} Pr (t_{k} | c_{x}) \cdot Pr (t_{k} | d_{i})) \cdot (\sum_{\forall t_{k}} Pr (t_{k} | c_{x}) \cdot Pr (t_{k} | u_{q}))}

5.3. Conventional collaborative filtering

As addressed in Section 2.2, CCF can be classified into UCF and ICF. However, as the quality of UCF is higher than that of ICF, we focus on UCF in this work. Thus, CCF represents UCF approaches hereafter. In general, CCF consists of two steps [18, 19]. First, it identifies like-minded users whose preferences are similar to those of the given user (i.e. the active user). The users’ preferences can be derived from explicit feedback such as rating scores or implicit feedback such as click-through rates on documents. However, if an active user does not provide any rating scores, it is difficult to compute the degrees of relevance between an active user and like-minded users. Therefore, some CF approaches exploit implicit feedback derived from users’ click-through logs. Second, CF recommends documents that like-minded users have accessed in the past but the active user has not yet accessed.

In the first step, to estimate the degree of relevance between users, CCF exploits exact matching of documents that users accessed. Only users that have accessed the same documents are considered like-minded users. In Figure 4(c), suppose that two users (i.e. an active user with preference $u_{p}$ and a like-minded user with preference $u_{r}$ ) only accessed a document $d_{i}$ . As a result, the preference of the active user is assumed to be similar to that of the like-minded user. Thus, the document $d_{r}$ that only the like-minded user accessed is recommended to the active user. As shown in Figure 5(c), entity types such as users and documents are used to correlate an active user’s preference with a document in CCF.

In CCF, the probability of recommending a document $d_{r}$ to the active user with preference $u_{p}$ , can be estimated as follows:

\Pr_{c c f} (d_{r} | u_{p}) \propto \sum_{\forall u_{r}} Pr (u_{r} | d_{r}) \cdot Pr (u_{r} | u_{p}) \propto \sum_{\forall u_{r}} Pr (u_{r} | d_{r}) \cdot {\sum_{\forall d_{i}} Pr (d_{i} | u_{r}) \cdot Pr (d_{i} | u_{p})}

(16)

In equation (16), $d_{i}$ represents a document accessed in common by two users. The document $d_{i}$ should not be confused with the document that was only accessed by the user $u_{r}$ , which is denoted by $d_{r}$ . In CCF, two users’ preferences (i.e. $u_{p}$ and $u_{r}$ ) are correlated by documents that they have accessed. Therefore, the probability $Pr (u_{r} | u_{p})$ , which represents an implicit relationship between two users, can be derived from explicit relationships such as user–document relationships.

5.4. Semantic collaborative filtering

To estimate the degree of relevance between users, CCF exploits the exact matching of documents accessed by users. However, this causes the sparsity problem. That is, users are considered unlike-minded users in CCF even though they may be semantically like-minded. To resolve this problem, we map users’ preferences to their corresponding concepts to represent their semantics in semantic collaborative filtering (SCF) [43, 44]. In SCF, like-minded users are identified by exploiting the exact matching of concepts derived from users’ preferences. As a result, it is possible to find like-minded users although they have accessed different documents.

Similar to CCF, SCF also consists of two steps: the first is to identify like-minded users and the second is to recommend documents that like-minded users have accessed in the past. The main difference between CCF and SCF is the method of identifying the like-minded users. CCF exploits the matching of documents that users have accessed, whereas SCF exploits the matching of concepts that users prefer. The concepts are derived from the users’ access logs. In Figure 4(d), suppose that two users (i.e. an active user with preference $u_{p}$ and a like-minded user with preference $u_{r}$ ) prefer a concept $c_{x}$ . As a result, the preference of the active user is assumed to be semantically similar to that of the like-minded user. The document $d_{r}$ that only the like-minded user has accessed is recommended to the active user. This process is identical to that of CCF. As shown in Figure 5(d), entity types such as users and concepts are used to correlate an active user’s preference with a document in SCF, whereas users and documents are used in CCF. In SCF, the probability of recommending a document $d_{r}$ to the active user with preference $u_{p}$ can be estimated as follows:

\Pr_{s c f} (d_{r} | u_{p}) \propto \sum_{\forall u_{r}} Pr (u_{r} | d_{r}) \cdot Pr (u_{r} | u_{p}) \propto \sum_{\forall u_{r}} Pr (d_{r} | u_{r}) \cdot {\sum_{\forall c_{x}} Pr (c_{x} | u_{r}) \cdot Pr (c_{x} | u_{p})}

(17)

5.5. Hybrid approaches to semantic search and recommendation

Because of the generality and flexibility of the proposed framework, conventional search and recommendation approaches can be adapted to it. By unifying search and recommendation approaches, we can utilize the personalized authority of documents.

By modifying the entity types and their relationships, the possible unified approaches for search and recommendation can be classified into 15 approaches, which are shown in Figure 6. To the best of our knowledge, the conventional approaches cover only five of these, which are indicated in Figure 6. Furthermore, owing to the generality of the proposed framework, other semantic search (or recommendation) approaches can be modelled in the framework by modifying the entity types. For example, in context-aware search, context entities can be added to the proposed framework.

The ranking function for hybridizing search and recommendation can be defined as follows:

{Pr}_{uni} (d_{i} | u) = γ \cdot {Pr}_{search} (d_{i} | u_{q}) + (1 - γ) \cdot \Pr_{c f} (d_{i} | u_{p})

(18)

where the symbol $u$ represents a user’s needs, which consists of a query (denoted by $u_{q}$ ) and a preference (denoted by $u_{q}$ ). In equation (18), Pr_search(d_i|u_q) is the combination of keyword search and semantic search, and Pr_cf(d_i|u_p) is the combination of CCF and SCF. The probabilities Pr_search(d_i|u_q) and Pr_cf(d_i|u_p) can be rewritten as follows:

{Pr}_{search} (d_{i} | u_{q}) = α \cdot {Pr}_{ks} (d_{i} | u_{q}) + (1 - α) \cdot \Pr_{S S} (d_{i} | u_{q})

(19)

{Pr}_{cf} (d_{i} | u_{q}) = β \cdot \Pr_{c c f} (d_{i} | u_{p}) + (1 - β) \cdot {Pr}_{scf} (d_{i} | u_{p})

(20)

6. Experiments

In order to evaluate the proposed framework, we have used two kinds of domain knowledge bases: ODP web directory and Wikipedia. The ODP web directory consists of 49,334 terms and 11,584 concepts whose distance from the domain root concept ‘Top/Arts/Music/’ is within nine. Wikipedia consists of 46,422 terms and 11,768 concepts whose distance from the domain root concept ‘http://en.wikipedia.org/wiki/Music’ is within seven. As relevant concepts are linked to each other through article links in Wikipedia [45], a large number of domain concepts are collected by iteratively visiting the lower concepts adjacent to the upper concepts, starting from the domain root concept. Since hyperlinks in Wikipedia represent various semantic relationships, the crawled concepts might be irrelevant to music. Thus, we have manually eliminated non-taxonomic relationships in the crawled concepts of Wikipedia. In general, a user’s access (i.e. listening) time in the music domain is shorter than those in other domains (e.g. movies and books), and a user may listen to the same track many times [46]. As a result, the volume of a user’s access logs for a certain period will be relatively large. As collecting access logs and analysing users’ preferences in the music domain are easier than in other domains, the music domain has been widely used to confirm the effectiveness of search (or recommendation) systems [47]. A total of 9394 users’ listening logs were crawled from last.fm (http://www.last.fm). Of these, 100 users were assigned as active users to evaluate the proposed search and CF approaches, and the rest users were assigned as the candidates of like-minded users to evaluate CF approaches. This is because, according to Lee et al. [44], CF approaches provide the most accurate recommendation results when the number of like-minded users is between 10 and 15. In the crawled access logs, the number of distinct documents that the active users have accessed is 20 on average. To evaluate the top-10 search (or recommendation) results, we used 50% of the given data as training data. Active users are assumed to perform searching (or recommending) documents, and their information needs are learned from the training set; as a result, they are given the reasonable documents that reflect their needs. For experiments, 22,216 tracks crawled from last.fm were considered documents. Each track consists of several attributes (i.e. title, artist name, album name, genre, artist type, country and description). However, because we consider a document a term vector, the attribute types are ignored in this work. Hence, the proposed approach can be applied to any contents regardless of content types such as music, movie and book, particularly in the Internet or digital library environments.

To evaluate the performance of proposed approaches, many studies have used recall as well as precision. However, as semantic approaches can find documents that do not contain the keywords derived from users’ needs, they have high recall in general. Therefore, many semantic approaches have attempted to enhance the degree of precision rather than recall. In this context, for performance evaluation, we introduce two more reasonable performance measures: precision_k and inverse rank precision_k. Precision_k is defined as follows:

precisio n_{k} = \frac{Number of documents that a user accessed in top k}{k}

precision_k is used to examine how many documents accessed by a user are retrieved in top-k results. Inverse rank precision_k is to improve mean reciprocal rank [44] as a measure widely used in evaluating information retrieval systems, which is defined as the average of the reciprocal ranks of query responses. Inverse rank precision_k is the weighted reciprocal ranks over a query, which is defined as follows:

inverse rank precisio n_{k} = \frac{\sum_{k} \frac{1}{rank of a result according to a user ’ s preference}}{\sum_{k} 1 / 1 k k}

As an example to explain the difference between precision_k and inverse rank precision_k, Table 1 shows the correct ranks of documents and the rank of the documents according to a user’s preference in different approaches. The correct ranks are estimated by the user’s click-through counts for documents. If we assume that the approaches return top-three documents to the user, ‘By the way’ and ‘Bad day’ are provided to the user in this example. This is because their ranks are less than or equal to 3 in each approach. As the number of documents that the user accessed in top-three results is 2, the precision₃ values of approaches A and B are 2/3 = 0.67.

Table 1.

Ranks of documents according to a user’s preference.

Document	Correct Rank	Rank according to preference
		Approach ‘A’	Approach ‘B’
By the way	1	2	1
Bad day	2	1	3
Go to sleep	3	4	6

The inverse rank precision₃ values of approaches A and B are estimated as follows:

inverse rank precisio n_{3} of A = \frac{\frac{1}{2} + \frac{1}{1}}{\frac{1}{1} + \frac{1}{2} + \frac{1}{3}} = 0.819

inverse rank precisio n_{3} of B = \frac{\frac{1}{1} + \frac{1}{3}}{\frac{1}{1} + \frac{1}{2} + \frac{1}{3}} = 0.728

The inverse rank precision₃ of the approach A is larger than that of the approach B. Thus, we can say that model A reflects a user’s top-ranked preference better than model B, although they show the same value in a user’s overall preferences. That is, precision_k measures how much the approach considers users’ overall preferences, whereas inverse rank precision_k measures how much the approach considers users’ top-ranked preferences. The closer inverse rank precision_k gets to 1.0, the more the results match users’ top-ranked preferences.

Table 2.

Categorization of search and recommendation approaches for performance comparison.

Approaches		Description
Search	Keyword search (KS)	KS finds documents that are exactly matched to a given query. Keywords (or index terms) are used to correlate a given query with documents.
	Semantic search (SS)	Tag_SS	Since a user’s query and documents are represented by a set of tags, the degrees of relevance are estimated by the exact matching of tags; i.e., tags are used to correlate the query with documents. As some studies regard tags as concepts derived from folksonomy, we also regard Tag_SS as a sort of semantic search. The implementation is based on the approach of Xu et al [3].
		ODP_SS	A user’s query and documents are represented by a set of categories that are regarded as ‘concepts’ in this paper. The categories are used to correlate the query with documents. The degrees of relevance between a query and documents are estimated by the conceptual matching
		Wiki_SS	The topics of Wikipedia are regarded as concepts. Therefore, the topics are used to correlate a query with documents. The rest of techniques used in Wiki_SS are identical to those in ODP_SS.
Collaborative filtering (CF)	Conventional CF (CCF)	Measuring the angular difference of two users’ preference vectors that are measured from the mean. CCF is based on Pearson’s correlation coefficient, and it exploits the exact matching of documents to estimate the degrees of relevance between users. The implementation is based on the approach of Ahn [24].
	Semantic CF (SCF)	Tag_SCF	Since the users’ preferences and documents are represented by a set of tags, and the degrees of relevance between users are estimated by tags users annotated. Tag_SCF regards tags as concepts. The implementation is based on the approach of Kim et al. [34].
		ODP_SCF	The concepts in ODP_SCF consist of categories extracted from the ODP web directory. Users’ preferences and documents are mapped to their corresponding concepts. The degrees of relevance between users are estimated by the concept matching, and the concepts are derived from the documents that users accessed. The implementation is described in Lee et al. [43].
		Wiki_SCF	The concepts in Wiki_SCF consist of topics extracted from Wikipedia. The rest techniques used in Wiki_SCF are identical to those in ODP_SCF. The details of the implementation are described in Lee et al. [43] and [44].

In the following sections, the various properties of the search, CF and hybrid approaches are investigated. Specifically, in experiments on the hybrid approaches, we investigate the effect of the document authority derived from CF. Each test is repeated five times and the mean values are reported (i.e. mean precision₁₀ and mean inverse rank precision₁₀) for more reliable results.

6.1. Search

6.1.1. Comparison of search approaches with varying number of entities

When estimating the relevance between a user’s query and documents, it is critical to determine the number of entities that correlate the user’s query and documents; the overhead (e.g. execution time) increases with an increasing number of entities. For example, in equation (15) for semantic search, the number of concepts increases the overhead for finding documents. As addressed in Section 5, only keywords are used to correlate a user’s query and documents in keyword search. On the other hand, terms and concepts are used to correlate the query and documents in semantic search. According to our statistical analysis, as concept–document relationships are denser than other relationships, it is feasible to observe the effect of the number of concepts mapped to documents, as shown in Figure 7.

The maximum number of concepts in ODP_SS and Wiki_SS ranges from 100 to 10,000. Furthermore, the maximum number of keywords and tags in KS and Tag_SS ranges from 10 to 100; the values in parentheses on the x-axis represent the number of keywords in KS or the number of tags in Tag_SS. Furthermore, the notation ‘full’ indicates that the maximum number of concepts mapped to documents is not determined. The experiment result indicates that mean precision₁₀ and mean inverse rank precision₁₀ do not significantly increase as the number of concepts mapped to a document increases.

6.1.2. Comparison of search approaches with varying α

As shown in equation (19), we assume that the rank of a document is determined by semantic search as well as keyword search. That is, two entity types are utilized to estimate the degree of relevance between a query and a document, which are keywords and concepts. In the hybrid search approaches, the results derived from keyword search and semantic search are merged to generate a final ranked document list. Figure 8 shows the mean precision₁₀ and mean inverse rank precision₁₀ of various search approaches with varying α. If the weight α is zero, the rank function considers only semantic search for ranking documents. In addition, if the weight α is 1, the function only considers keyword search.

While the weight α is less than 0.4, mean precision₁₀ and mean inverse rank precision₁₀ in KS+Tag_SS increase sharply compared with those in KS+ODP_ SS and KS+Wiki_SS. This is because the search results in KS are already included in semantic search such as ODP_SS and Wiki_SS. However, as KS has more weight, the values mean precision₁₀ and mean inverse rank precision₁₀ decrease significantly in all search approaches.

6.2. Collaborative filtering

6.2.1. Comparison of CF approaches with varying number of concepts

When representing a user’s preference and documents as the concepts of domain knowledge, it is critical to determine the number of concepts mapped to the user’s preference and documents; that is, the number of concepts for a user’s preference may affect the quality as well as performance. For example, if the number of concepts for a user’s preference increases, it is difficult to find like-minded users and to make a recommendation list in real time. Furthermore, the number of concepts may alter semantically like-minded users. Thus, in this section, we discuss the effects of the number of concepts mapped to a user’s preference.

Figure 9 shows the effects of the number of concepts in CF approaches with mean precision₁₀ and mean inverse rank precision₁₀. Particularly, in ODP_SCF and Wiki_SCF, the number of concepts ranges from 500 to 10,000. On the other hand, in Tag_SCF, the number of concepts (i.e. tags) ranges from 100 to 1000; the values in parentheses on the x-axis represent the number of concepts in Tag_SCF. As shown in Figure 9, mean precision₁₀ and mean inverse rank precision₁₀ are saturated when the maximum number of concepts is larger than about 4000 in ODP_SCF and Wiki_SCF. Otherwise, they are proportional to the number of concepts. However, in Tag_SCF, the performance values do not increase significantly with the number of concepts because the degree of sparsity is not significantly improved. The sparsity is measured as the ratio of empty links in the possible links (or relationships) between two entity types. A comparison of sparsity is shown in Table 3.

Table 3.

Sparsity with varying number of concepts.

Number of concepts		Sparsity of ‘concept–user relationships’
ODP_SCFWiki_SCF	Tag_SCF	ODP_SCF	Wiki_SCF	Tag_SCF
500	—	0.9568	0.9575	—
1000	100	0.9136	0.9150	0.9859
2000	200	0.8271	0.8300	0.9771
3000	300	0.7407	0.7451	0.9723
4000	400	0.6543	0.6603	0.9697
5000	500	0.5698	0.5760	0.9689
6000	600	0.4912	0.4931	0.9675
7000	700	0.4919	0.4143	0.9671
8000	800	0.3636	0.3437	0.9670
9000	900	0.3179	0.2846	0.9670
10,000	1000	0.2908	0.2406	0.9668
Full	Full	0.2827	0.2139	0.9668

6.2.2. Comparison of CF approaches with varying β

We assume that like-minded users are identified by the matching of documents accessed by users as well as the matching of concepts preferred by the users. CCF estimates the degree of relevance between users via document matching, whereas SCF estimates the degree of relevance via concept matching.

The results derived from CCF and SCF are merged to generate a final document list for an active user, which is expressed by equation (20). Figure 10 shows the mean precision₁₀ and mean inverse rank precision₁₀ of CF approaches with varying β. If the weight is zero, the rank function only utilizes SCF to recommend documents. While the weight is greater than 0.3, mean precision₁₀ and mean inverse rank precision₁₀ decrease in SCF. That is, as CCF has more weight, the results of CCF are considered noise. As addressed in Section 2.2, because CCF has the sparsity problem, its recommendation quality is poorer than that of SCF.

6.3. Hybridizing search with collaborative filtering

As search approaches exploit the exact matching of entities such as keywords or concepts between a query and a document, the derived degree of relevance is referred to as the content-based relevance. Sometimes, it is difficult to rank documents if they have the same degree of content-based relevance with the given query. Thus, it is necessary to consider the relevance derived from a non-content aspect such as the authority of documents. The authorities of documents are derived from CF in this work. Therefore, in the hybrid approaches, heterogeneous entity types such as users, terms (or keywords), concepts and documents are used to correlate a user’s needs with documents. In this section, we compare hybrid approaches of search and CF according to weight $γ$ , which is used in equation (18).

The semantic search and SCF approaches shown in Figure 11 exploit the topics of Wikipedia as concepts. The results shown in the figure are similar to those of other concepts (such as categories of the ODP web directory and tags of folksonomy). Owing to space limitations, the results are abbreviated in this work. Figure 11 shows the mean precision₁₀ and mean inverse rank precision₁₀ of hybrid approaches with varying weight $γ$ . When the weight $γ$ is between 0 and 1 (i.e. 0 < $γ$ < 1), the values of mean precision₁₀ and mean inverse rank precision₁₀ represent their maximum values at the given interval. In this experiment, when the weight $γ$ is between 0.5 and 0.9, the mean precision₁₀ and mean inverse rank precision₁₀ are the highest.

The experiment result indicates that the performance of hybrid approaches also improves with an increasing number of entity types. However, the improvement is not significant. There are no significant differences between the results derived from Wiki_SS+Wiki_SCF and KS+ Wiki_SS+CCF+Wiki_SCF. This is because the results of KS and CCF are already included in Wiki_SS and Wiki_SCF. By analysing the sparsity, we observe that the sparsity under a threshold (about 0.6) does not further improve the quality of search approaches. The hybrid approaches, which use the authority of documents derived from CF, have higher mean precision10 and mean inverse rank precision10 values than other approaches.

6.4. Discussion

Through the extensive experiments using the music domain data, we have shown that the quality of search and recommendation approaches can be improved by effectively using heterogeneous entities and their relationships under the probabilistic framework. Normally, to evaluate search (or recommendation) systems trustworthily is not easy and always controversial in the field of information retrieval. In this context, this section describes several considerations for relevance judgment, test data and execution time.

When evaluating search and recommendation methods, one of critical issues is how to correctly judge the relevance between users’ information needs and their actual search results. In general, the relevance judgment is classified into two approaches: user-based judgment [48] and log-based judgment [49]. The user-based judgment approach (which includes nDCG (normalized discounted cumulative gain)) requires a large number of users owing to individual relevance judgments on search results, and thus its corresponding experiments are very costly. Moreover, since the users involved in the experiments recognize that they are being tested, they may bias the experiment results [3]. In contrast, the log-based judgment approach entails lower costs and smaller biases than the user-based judgment approach. However, this approach needs to collect large amounts of query logs for experiments. Actually, since most search engines such as Google and Yahoo! do not release their query logs to protect users’ privacy, it is highly difficult to collect sufficient query log data so as to evaluate search (or recommendation) methods. Therefore, as for relevance judgment, we assume that a user who accessed a particular document is related to the keywords contained in the document. For example, suppose a user listened to a track ‘yesterday’ of ‘the Beatles’, then the user is assumed to be related to the keywords such as ‘British’, ‘class’ and ‘sad’ which are contained in the description of the track; that is, we assume that the user submits a query with such keywords in order to find the track ‘yesterday’ of ‘the Beatles’.

As stated before, a user’s access time in the music domain is short, and users tend to listen to the same track at many times. As a result, the number of a user’s access logs for a certain period is easily made to increase, and analysing a user’s preference in the music domain is not a difficult job. Since the experimental data and results belong only to the music domain, the observation of a threshold of sparsity and the weights of α, β and γ cannot be directly applied to other domains such as movie and book. However, we expect that our experimental observations are starting bases for determining the number of entities and tuning the probabilistic ranking functions.

In representing documents and a user’s information needs, it is very important to determine the number of entities to clearly represent the semantics with several entities. As shown in the experiments, the number of entities mapped to a user’s information needs is more critical than that mapped to documents. As the number of entities increases, the execution time may increase enough to make the system impractical. This can be a challenging problem to be resolved when the proposed framework is applied to real systems; basically, to reduce the execution time, we need to devise a special index structure suitable for a heterogeneous graph.

7. Conclusion

In this paper, we have proposed a probabilistic framework to unify semantic search and recommendation, in which heterogeneous entities such as users, terms, concepts and documents are handled in a probabilistic manner. Its critical issues include how to model the explicit (or implicit) relationships between heterogeneous entities and how to estimate the relevance between a document and a user’s information needs. In our work, we have adopted a probabilistic graph approach for modelling relationships between entities, and thus we could achieve a clear formalism in estimating the relevance. The unified framework offers three improvements over the previous studies owing to its generality and flexibility: (1) first, enriching semantics of documents and users’ needs with keywords and concepts results in resolving the sparsity and semantic ambiguity problems; (2) second, using the personalized authority of documents helps to improve the quality of search results; (3) and third, the proposed framework makes it possible to hybridize search approaches (i.e. keyword search and semantic search) and CF (i.e. CCF and SCF) ones. That is, previous studies can be considered as special cases in the unified framework, and furthermore additional search and recommendation methods can be easily constructed according to a user’s circumstances. Our extensive experiments have shown that the proposed approach outperforms conventional search and CF-based recommendation approaches by resolving their sparsity, semantic ambiguity and non-personalized authority problems. Now, we are trying to further improve the quality of search and recommendation with context information such as time and location.

Footnotes

Acknowledgements

This work was supported by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education, Science and Technology (grant number: NRF-2010-0025212).

Notes

References

Carmel

Roitman

Yom-Tov

. Social bookmark weighting for search and recommendation. The VLDB Journal 2010; 19(6): 761–775.

Ding

Orlowska

. A Recommendation system with interest-drifting. Lecture Notes in Computer Science, Vol. 4831. Berlin: Springer, 2007, pp. 633–642.

Bao

Fei

. Exploring folksonomy for personalized search. Proceedings of ACM conference on research and development in information retrieval (SIGIR’08) 2008, pp. 155–162.

Mobasher

Jin

Zhou

. Semantically enhanced collaborative filtering on the Web. Lecture Notes in Computer Science, Vol. 3209. Berlin: Springer, 2004, pp. 57–76.

Park

Pennock

. Applying collaborative filtering techniques to movie search for better ranking and browsing. Proceedings of ACM conference on knowledge discovery and data mining (SIGKDD’07) 2007, pp. 550–559.

Lenat

Guha

. Building large knowledge based systems. Boston, MA: Addison-Wesley Longman, 1990.

Fikes

Hayes

Horrocks

. OWL-QL: A language for deductive query answering on the Semantic Web. Journal of Web Semantics 2004; 2(2): 1–11.

Kim

. ONTOWEB: Implementing an ontology-based web retrieval system. Journal of the American Society for Information Retrieval and Technology 2005; 56(11): 1167–1176.

Lee

Shim

Lee

. A pragmatic approach to model and exploit the semantics of product information. Journal on Data Semantics 2006; 7: 242–266.

10.

Balmin

Hristidis

Papakonstantinou

. ObjectRank: Authority-based keyword search in databases. Proceedings of of the 30th international conference on very large data bases (VLDB’04) 2004: 564–575.

11.

Guha

McCool

Miller

. Semantic search. Proceedings of of the 12th International World Wide Web Conference (WWW’03), 2003, pp. 700–709.

12.

Rocha

Schwabe

Aragao

. A hybrid approach for searching in the Semantic Web. Proceedings of of the 13th international World Wide Web conference (WWW’04), 2004, pp. 374–383.

13.

Lee

Kim

Lee

. Exploiting taxonomic knowledge for personalized search: A Bayesian belief network-based approach. Journal of Information Science and Engineering 2011; 25(4): 1413–1433.

14.

Castells

Fernandez

Vallet

. An adaptation of the vector space model for ontology-based information retrieval. IEEE Transactions on Knowledge and Data Engineering 2007; 18: 261–272.

15.

. Exploring social annotations for the Semantic Web. Proceedings of of the 15th international World Wide Web conference (WWW’06), 2006, pp. 417–426.

16.

Xuefeng

. A hybrid collaborative filtering method for multiple-interests and multiple-content recommendation in e-commerce. Expert Systems with Applications 2005; 28: 67–77.

17.

Wang

Vries

Reinders

. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. Proceedings of ACM conference on research and development in information retrieval (SIGIR’06), 2006, pp. 501–508.

18.

Resnick

Iacovou

Suchak

Bergstorm

Riedel

. GroupLens: An open architecture for collaborative filtering of Netnews. Proceedings of of ACM conference on computer supported cooperative work, 1994, pp. 175–186.

19.

Herlocker

Konstan

Borchers

Riedl

. An algorithmic framework for performing collaborative filtering. Proceedings of ACM conference on research and development in information retrieval (SIGIR’ 99), 1999, pp. 230–237.

20.

Jin

Chai

. An automatic weighting scheme for collaborative filtering. Proceedings of ACM conference on research and development in information retrieval (SIGIR’04), 2004, pp. 337–344.

21.

Deshpande

Karypis

. Item-based top-N recommendation algorithm. ACM Transactions on Information Systems 2004; 22: 143–177.

22.

Sarwar

Karypis

Konstan

Riedl

. Item-based collaborative filtering recommendation algorithms. Proceedings of of the 10th international World Wide Web conference (WWW’01), 2001, pp. 285–295.

23.

Mild

Natter

. A critical view on recommendation systems. Work Paper Series (Vienna University of Economics and Business Administration), 2001.

24.

Ahn

. A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem. Information Sciences 2008; 178(1): 37–51.

25.

Breese

Heckerman

Kadie

. Empirical analysis of predictive algorithms for collaborative filtering. Proceedings of of the 14th conference of uncertainty in artificial intelligence (UAI’98), 1998, pp. 43–52.

26.

Billsus

Pazzani

. Learning collaborative information filters. Proceedings of of the 15th international conference on machine learning (ICML’98), 1998, pp. 46–54.

27.

Sarwar

Karypis

Konstan

Riedl

. Application of dimensionality reduction in recommender system – a case study. Proceedings of of ACM WebKDD Workshop, 2000.

28.

Khoshgoftaar

. A survey of collaborative filtering techniques. Advances in Artificial Intelligence 2009; 4: 1–19.

29.

Balabanovic

Shoham

. Fab: Content-based, collaborative recommendation. Communication of the ACM 1997; 40(3): 66–62.

30.

Pazzani

. A Framework for collaborative, content-based and demographic filtering. Artificial Intelligences Review 1999; 13(5–6): 393–408.

31.

Ungar

Foster

. Clustering methods for collaborative filtering. Proceedings of of Workshop on Recommendation Systems, 1998.

32.

Chee

Han

Wang

. RecTree: An efficient collaborative filtering method. Proceedings of of the 3rd international conference on data warehousing and knowledge discovery (DaWak’01), 2001, pp. 141–151.

33.

Zanardi

Capra

. Social ranking: Uncovering relevant content using tag-based recommender systems. Proceedings of of the 2008 ACM conference on recommender systems (RecSys’08), 2008, pp. 51–58.

34.

Kim

. Collaborative filtering based on collaborative tagging for enhancing the quality of recommendation. Electronic Commerce Research and Application 2010; 9: 73–83.

35.

Chong

David

. Collaborative topic modeling for recommending scientific articles. Proceedings of ACM conference on knowledge discovery and data mining (SIGKDD’11), 2011, pp. 448–456.

36.

David

Andrew

Michael

. Latent Dirichlet allocation. Journal of Machine Learning Research 2003; 3: 993–1022.

37.

Wolfman

, Term co-occurrence in internet search engine queries: An analysis of the Excite data set. Canadian Journal of Information and Library Science 1999; 24: 12–33.

38.

Baeza-Yates

Ribeiro-Neto

. Modern information retrieval, 2nd edn. New York: Addison-Wesley, 1999.

39.

Porter

. An algorithm for suffix stripping. Readings of Information Retrieval 1997: 313–316.

40.

Priss

. Formal concept analysis in information science. Annual Review of Information Science and Technology 2006; 40: 1–22.

41.

Shao

Zhang

. Approximation in formal concept analysis. Lecture Notes in Computer Science, Vol. 3641. Berlin: Springer, 2005, pp. 43–53.

42.

Wong

SKM

Yao

. On Modeling information retrieval with probabilistic inference. ACM Transactions on Information Systems 1995; 13: 38–68.

43.

Lee

Kim

Lee

. Conceptual collaborative filtering recommendation: A probabilistic learning approach. Neurocomputing 2010; 73: 2793–2796.

44.

Lee

Kim

. A probabilistic approach to semantic collaborative filtering using world knowledge. Journal of Information Science 2011; 37: 49–66.

45.

Wang

Lochovsky

Sun

Chen

. Understanding user’s query intent with Wikipedia. Proceedings of of the 18th international World Wide Web conference (WWW’09), 2009, pp. 471–480.

46.

Celma

Herrera

. A new approach to evaluating novel recommendations. Proceedings of of the 2008 ACM conference on recommender systems (RecSys’08), 2008, pp. 179–186.

47.

Kim

Park

Lee

. A music recommendation system with a dynamic K-means clustering algorithm. Proceedings of of the 6th international conference on machine learning and applications (ICMLA’07), 2007, pp. 399–403.

48.

Pant

Sheng

. Interest-based personalized search. ACM Transactions on Information Systems 2007; 5: 1–38.

49.

Sieg

Mobasher

Burke

. Web search personalization with ontological user profiles. Proceedings of of ACM conference on information and knowledge management (CIKM’07), 2007, pp. 525–534.