ARTICLE N PRESS Information Sciences xxx(2011)xXx Contents lists available at Science Direct Information sciences ELSEVIER journalhomepage:www.elsevier.com/locate/ins Exploring synergies between content-based filtering and spreading Activation techniques in knowledge-based recommender systems Yolanda blanco-Fernandez, Martin Lopez-Nores, Alberto Gil-Solla, Manuel Ramos-Cabrer, Jose j. Pazos-aria ETSE Telecomunicacion, Campus Universitario, Vigo 36310, Spain ARTICLE INFO A BSTRACT mation overload by selecting automatically items that Received in revised form 9 June 2011 suggest item Accepted 10 June 2011 to those the user liked in the past, using syntactic matching mecha- nisms. The ri Available online xxxx of such mechanisms leads to re nding only items that bear rong resemblance to those the user already knows. Traditional collaborative approaches face up to overspecialization by considering the preferences of other users, which causes ther severe limitations. In this paper, we avoid the intrinsic pitfalls of collaborative solu- fltering tions and diversify the recommendations by reasoning about the semantics of the users preferences. Specifically, we present a novel content-based recommendation strategy that Spreading Activation techniques resorts to semantic reasoning mechanisms adopted in the Semantic Web, such as Spread- ng Activation techniques and semantic associations. We have adopted these mechanisms extra knowledge about the users preferences and leading to more accurate and diverse suggestions. Our approach is generic enough to be used in a wide variety of domains and recommender systems. The proposal has been preliminary evaluated by statistics- driven tests involving real users in the recommendation of Digital TV contents. The results reveal the users' satisfaction regarding the accuracy and diversity of the reasoning-driven ontent-based recommendations e 2011 Elsevier Inc. All rights reserved. 1 Introduction Recommender systems provide personalized advice to users about items they might be interested in. These tools are already helping people efficiently manage content overload and reduce complexity To fulfill these personalization needs, three main components are required: (i)a database that stores characterizations of the available items, (ii) profiles that model the users' preferences, and (iii)recommendation strategies that make personalized uggestions to each individual. The first recommendation strategy was content-based filtering[ 41, 30, which consists of suggesting items similar to those the user liked in the past. In spite of its accuracy, this technique is limited due to the similarity metrics employed, which are based on rigid syntactic approaches that can only detect similarity between items that share all or some of their attributes [1. Consequently, traditional content-based approaches lead to overspecialized suggestions including only items that bear strong resemblance to those the user already knows (i.e. items bound to the attributes defined in his her profile ). Work funded by the ministerio de educacion y Ciencia(Gobierno de Espana) Research Project tiN 0020-0255S-see front matter a 2011 Elsevier Inc. All rights reserved. doi:10.1016ins201106.016 Please cite this article in press as:Y. Blanco-Fernandez et al, Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci.(2011). doi: 10.1016)jins2011.06.016
Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems q Yolanda Blanco-Fernández ⇑ , Martín López-Nores, Alberto Gil-Solla, Manuel Ramos-Cabrer, José J. Pazos-Arias ETSE Telecomunicación, Campus Universitario, Vigo 36310, Spain article info Article history: Received 21 September 2009 Received in revised form 9 June 2011 Accepted 10 June 2011 Available online xxxx Keywords: Personalization Content-based filtering Semantic reasoning Spreading Activation techniques abstract Recommender systems fight information overload by selecting automatically items that match the personal preferences of each user. The so-called content-based recommenders suggest items similar to those the user liked in the past, using syntactic matching mechanisms. The rigid nature of such mechanisms leads to recommending only items that bear strong resemblance to those the user already knows. Traditional collaborative approaches face up to overspecialization by considering the preferences of other users, which causes other severe limitations. In this paper, we avoid the intrinsic pitfalls of collaborative solutions and diversify the recommendations by reasoning about the semantics of the user’s preferences. Specifically, we present a novel content-based recommendation strategy that resorts to semantic reasoning mechanisms adopted in the Semantic Web, such as Spreading Activation techniques and semantic associations. We have adopted these mechanisms to fulfill the personalization requirements of recommender systems, enabling to discover extra knowledge about the user’s preferences and leading to more accurate and diverse suggestions. Our approach is generic enough to be used in a wide variety of domains and recommender systems. The proposal has been preliminary evaluated by statisticsdriven tests involving real users in the recommendation of Digital TV contents. The results reveal the users’ satisfaction regarding the accuracy and diversity of the reasoning-driven content-based recommendations. 2011 Elsevier Inc. All rights reserved. 1. Introduction Recommender systems provide personalized advice to users about items they might be interested in. These tools are already helping people efficiently manage content overload and reduce complexity when searching for relevant information. To fulfill these personalization needs, three main components are required: (i) a database that stores characterizations of the available items, (ii) profiles that model the users’ preferences, and (iii) recommendation strategies that make personalized suggestions to each individual. The first recommendation strategy was content-based filtering [41,30], which consists of suggesting items similar to those the user liked in the past. In spite of its accuracy, this technique is limited due to the similarity metrics employed, which are based on rigid syntactic approaches that can only detect similarity between items that share all or some of their attributes [1]. Consequently, traditional content-based approaches lead to overspecialized suggestions including only items that bear strong resemblance to those the user already knows (i.e. items bound to the attributes defined in his/her profile). 0020-0255/$ - see front matter 2011 Elsevier Inc. All rights reserved. doi:10.1016/j.ins.2011.06.016 q Work funded by the Ministerio de Educación y Ciencia (Gobierno de España) Research Project TIN2010-20797. ⇑ Corresponding author. E-mail address: yolanda@det.uvigo.es (Y. Blanco-Fernández). Information Sciences xxx (2011) xxx–xxx Contents lists available at ScienceDirect Information Sciences journal homepage: www.elsevier.com/locate/ins Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016
ARTICLE N PRESS Y. Blanco-Ferndndez et aL Information Sciences xcx(2011)xxx-xXx In order to fight overspecialization, researchers devised collaborative filtering 36, 25, 29 -whose basic idea is to move be- d the experience of an individual user's profile and instead draw on the experiences of a community of like-minded users (his/her neighbors), and even they combined content-based and collaborative filtering in hybrid approaches [6, 22, 33, 13,.40 Even though collaborative(and hybrid) approaches mitigate the effects of overspecialization by considering the interests of other users, they bring in new limitations, such as the sparsity problem(related to difficulties to select each individuals neighborhood when the knowledge about the users' preferences is sparse), privacy concerns bound to the confidentiality of the users'personal data, and scalability problems stemmed from the management of many user profiles(instead of just one profile like in content-based approaches) The contribution of our paper is a content-based strategy that diversifies the recommendations by exploiting semantic rea- soning about the users interests, instead of considering other individuals preferences. This way, we overcome the overspe- cialization effects without suffering from the intrinsic limitations of collaborative and hybrid solutions. Specifically, our reasoning mechanisms have been borrowed from the area of the Semantic Web an initiative that is based on ()annotating Web resources by semantic annotations(metadata). (ii) formalizing this knowledge in a domain ontology that represents concepts and relationships by classes and properties, respectively, and (iii) carrying out reasoning processes about the onto- ogy in order to infer semantic relationships among the annotated resources. Broadly speaking, our content-based strategy suggests items which are semantically related to the users preferences, in- stead of offering items with the same attributes that appear in his/ her profile. For example, in the Tv field, a viewer who has enjoyed documentaries about traveling and archeology might receive as recommendations programs about potholing(a hob- by strongly related to the study of ancient graves)or about Greece (a country of deep-rooted archeological tradition).Our domain-independent strategy consists of two stages that adopt semantic associations 4 and Spreading Activation techniques henceforth, SA techniques)[14 as reasoning mechanisms: (1) Firstly, the pre-filtering phase selects an excerpt from the domain ont comprises only instances of classes and properties that are significant for the user(because they are closel his/her preferences). For the on, this excerpt is named the user's Ontology of Interest. Then, en semantic associations among the items included in the user's Ontology of Interest, starting from the hierarchical relationships and properties formal ed in it (2)Next, the recommendation phase processes the discovered knowledge and provides the personalized recommenda tions. To this aim, we emphasize the use of Sa techniques as computational mechanisms able to explore efficiently a generic network with nodes interconnected by links, and to detect concepts that are strongly related to each other. In our approach, the considered network corresponds to the users Ontology of Interest, while the strongly related nodes are his/ her preferences and the items to be suggested. The filtering criteria employed to delimit the users Ontology of Interest have been described in detail in [9]. For that rea son, here we focus on the second phase of our strategy. Specifically, our main research contribution consists of extending aim,our improved SA techniques must fulfill the following requirement. ecommender system can be considered. To this traditional Sa techniques so that the personalization requirements of a Firstly, our SA mechanisms must enable our strategy to discover useful knowledge for the recommendation proces reasoning about the semantics of the user's Ontology of Interest. Secondly, the knowledge inferred by the sa mechanisms must serve to increase the diversity of the offered content-based recommendations Lastly, our SA approach must learn automatically the user's preferences from the feedback provided after recommenda- tions, and thereafter update conveniently his her personal profile. This way, our reasoning-based suggestions evolve as the user's preferences change over time, thus reinforcing his/ her confidence in our personalization strategy. This paper is organized as follows. The next two sections provide necessary ba ound to understand our approach: Sec- tion 2 explains internals of semantic associations and highlights the limitations of traditional Sa techniques for personali zation purposes, while Section 3 presents the two essential components of our reasoning framework: the domain ontology and the user profiles. Next, Section 4 details the internals of our two-phase recommendation strategy exploring synergies between our improved Sa techniques and content-based filtering in the selection of diverse recommendations. Afterwards, Section 5 provides an example of our strategy in the scope of Digital TV, where we highlight how to exploit our reasoning capabilities to select Tv programs among the myriad available in the digital stream. Next, Section 6 presents the experimental evaluation of our approach and discusses scalability and computational feasibility concerns. Finally, Sec. tion 7 summarizes the conclusions from our work and motivates possible lines of further research. 2. Background on semantic reas In this section, we describe the internals of the semantic reasoning mechanisms exploited in our recommendation strat emantic associations and Sa techniques. Very briefly, the associations allow to interrelate the items available in the cite this article in press as: Y. Blanco-Fernandez et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci.(2011). doi: 10.1016/jins2011.06.016
In order to fight overspecialization, researchers devised collaborative filtering [36,25,29] – whose basic idea is to move beyond the experience of an individual user’s profile and instead draw on the experiences of a community of like-minded users (his/her neighbors), and even they combined content-based and collaborative filtering in hybrid approaches [6,22,33,13,40]. Even though collaborative (and hybrid) approaches mitigate the effects of overspecialization by considering the interests of other users, they bring in new limitations, such as the sparsity problem (related to difficulties to select each individual’s neighborhood when the knowledge about the users’ preferences is sparse), privacy concerns bound to the confidentiality of the users’ personal data, and scalability problems stemmed from the management of many user profiles (instead of just one profile like in content-based approaches). The contribution of our paper is a content-based strategy that diversifies the recommendations by exploiting semantic reasoning about the user’s interests, instead of considering other individuals’ preferences. This way, we overcome the overspecialization effects without suffering from the intrinsic limitations of collaborative and hybrid solutions. Specifically, our reasoning mechanisms have been borrowed from the area of the Semantic Web, an initiative that is based on (i) annotating Web resources by semantic annotations (metadata), (ii) formalizing this knowledge in a domain ontology that represents concepts and relationships by classes and properties, respectively, and (iii) carrying out reasoning processes about the ontology in order to infer semantic relationships among the annotated resources. Broadly speaking, our content-based strategy suggests items which are semantically related to the user’s preferences, instead of offering items with the same attributes that appear in his/her profile. For example, in the TV field, a viewer who has enjoyed documentaries about traveling and archeology might receive as recommendations programs about potholing (a hobby strongly related to the study of ancient graves) or about Greece (a country of deep-rooted archeological tradition). Our domain-independent strategy consists of two stages that adopt semantic associations [4] and Spreading Activation techniques (henceforth, SA techniques) [14] as reasoning mechanisms: (1) Firstly, the pre-filtering phase selects an excerpt from the domain ontology that comprises only instances of classes and properties that are significant for the user (because they are closely related to his/her preferences). For that reason, this excerpt is named the user’s Ontology of Interest. Then, we infer hidden semantic associations among the items included in the user’s Ontology of Interest, starting from the hierarchical relationships and properties formalized in it. (2) Next, the recommendation phase processes the discovered knowledge and provides the personalized recommendations. To this aim, we emphasize the use of SA techniques as computational mechanisms able to explore efficiently a generic network with nodes interconnected by links, and to detect concepts that are strongly related to each other. In our approach, the considered network corresponds to the user’s Ontology of Interest, while the strongly related nodes are his/her preferences and the items to be suggested. The filtering criteria employed to delimit the user’s Ontology of Interest have been described in detail in [9]. For that reason, here we focus on the second phase of our strategy. Specifically, our main research contribution consists of extending traditional SA techniques so that the personalization requirements of a recommender system can be considered. To this aim, our improved SA techniques must fulfill the following requirements: Firstly, our SA mechanisms must enable our strategy to discover useful knowledge for the recommendation process by reasoning about the semantics of the user’s Ontology of Interest. Secondly, the knowledge inferred by the SA mechanisms must serve to increase the diversity of the offered content-based recommendations. Lastly, our SA approach must learn automatically the user’s preferences from the feedback provided after recommendations, and thereafter update conveniently his/her personal profile. This way, our reasoning-based suggestions evolve as the user’s preferences change over time, thus reinforcing his/her confidence in our personalization strategy. This paper is organized as follows. The next two sections provide necessary background to understand our approach: Section 2 explains internals of semantic associations and highlights the limitations of traditional SA techniques for personalization purposes, while Section 3 presents the two essential components of our reasoning framework: the domain ontology and the user profiles. Next, Section 4 details the internals of our two-phase recommendation strategy, exploring synergies between our improved SA techniques and content-based filtering in the selection of diverse recommendations. Afterwards, Section 5 provides an example of our strategy in the scope of Digital TV, where we highlight how to exploit our reasoning capabilities to select TV programs among the myriad available in the digital stream. Next, Section 6 presents the experimental evaluation of our approach and discusses scalability and computational feasibility concerns. Finally, Section 7 summarizes the conclusions from our work and motivates possible lines of further research. 2. Background on semantic reasoning In this section, we describe the internals of the semantic reasoning mechanisms exploited in our recommendation strategy: semantic associations and SA techniques. Very briefly, the associations allow to interrelate the items available in the 2 Y. Blanco-Fernández et al. / Information Sciences xxx (2011) xxx–xxx Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016
ARTICLE N PRESS Y. Blanco-Fermandez et aL / Information Sciences xxx(2011)xXx-XXXx ecommender system, whereas the sa techniques serve to discover new knowledge about the users' preferences from the inferred associations and the concepts formalized in the domain ontology. 2.1. Semantic associations The semantic associations employed in our reasoning approach have been borrowed from (4, where Anyanwu and Sheth defined the relationships that can be established between two specific class instances in an ontology. In order to categorize these associations, they resorted to a structure named property sequence, which consists of a set of class instances linked to each other by means of properties. The first class instance defined in the sequence is the origin, the last one is the terminus. and the length of the sequence is the number of properties included in it. The semantic associations defined in [4]are defined next with the aid of Fig. 1 P-path association. Two class instances in and is are p-pathAssociated in an ontology if it is possible to find a property both classiisose origin is in and whose terminus is is(or vice versa ). Obviously, the longer the property sequence linking both class instances, the less significant the relationship between them, due to the presence of many intermediate nodes. p-join association. Two class instances are p-joinAssociated if both are origins(eg i, and is in Fig. 1)or terminus(is and i of two property sequences containing instances belonging to a common class c (named the union class). 2. 2. Spreading Activation techniques Sa techniques are computational mechanisms able to efficiently explore huge generic networks of nodes interconnected by links. According to the guidelines established in [14 these techniques work as follows: Each node is associated to a weight(called the activation level) that grows with its relevance in the network: the more levant the node, the higher its activation level. Besides, each link joining two nodes has a weight whose value is propor tional to the strength of the relationship existing between both nodes. Initially, a set of nodes are selected and the nodes connected with them by links(named neighbor nodes)are activated. In this process, the activation levels of the initially selected nodes are spread until reaching their neighbors in the network. The activation level of a reached node is typically computed by considering the levels of its neighbors and the weights assigned to the links that join them to each other. Consequently, the more relevant the neighbors of a given node (i.e. the higher their activation levels) and the stronger the relationship between the node and its neighbors (i.e. the higher the weights of the links between them). the more relevant the node will be in the network. The spreading process is repeated until reaching all the nodes of the network. In the end the highest activation levels correspond to the nodes that are most closely related to the initially selected ones. Since the spreading process permits to reach nodes that are not directly joined to the initially selected ones, Sa techniques carry out inference processes where new knowledge is learned. To harness these inferential capabilities, several algorithms have been proposed for exploration and extraction of the most significant concepts formalized in a knowledge network. In p-path (u, D Property Sequence: ps=[po, p, p2, p, ① ① p-JoIn q, D p-Join (s D i, i,: instances belonging to class C Fig. 1. Semantic associations adopted in our reasoning-driven approach. cite this article in press as: Y. Blanco-Fernandez et al, Exploring synergies between content-based filtering and Spreading Activation iques in knowledge-based recommender systems, Inform. Sci. (2011). doi: 10. 1016/j ins. 2011.06.016
recommender system, whereas the SA techniques serve to discover new knowledge about the users’ preferences from the inferred associations and the concepts formalized in the domain ontology. 2.1. Semantic associations The semantic associations employed in our reasoning approach have been borrowed from [4], where Anyanwu and Sheth defined the relationships that can be established between two specific class instances in an ontology. In order to categorize these associations, they resorted to a structure named property sequence, which consists of a set of class instances linked to each other by means of properties. The first class instance defined in the sequence is the origin, the last one is the terminus, and the length of the sequence is the number of properties included in it. The semantic associations defined in [4] are defined next with the aid of Fig. 1: q-path association. Two class instances i1 and i5 are q-pathAssociated in an ontology if it is possible to find a property sequence whose origin is i1 and whose terminus is i5 (or vice versa). Obviously, the longer the property sequence linking both class instances, the less significant the relationship between them, due to the presence of many intermediate nodes. q-join association. Two class instances are q-joinAssociated if both are origins (e.g. i1 and i6 in Fig. 1) or terminus (i5 and i8) of two property sequences containing instances belonging to a common class C (named the union class). 2.2. Spreading Activation techniques SA techniques are computational mechanisms able to efficiently explore huge generic networks of nodes interconnected by links. According to the guidelines established in [14], these techniques work as follows: Each node is associated to a weight (called the activation level) that grows with its relevance in the network: the more relevant the node, the higher its activation level. Besides, each link joining two nodes has a weight whose value is proportional to the strength of the relationship existing between both nodes. Initially, a set of nodes are selected and the nodes connected with them by links (named neighbor nodes) are activated. In this process, the activation levels of the initially selected nodes are spread until reaching their neighbors in the network. The activation level of a reached node is typically computed by considering the levels of its neighbors and the weights assigned to the links that join them to each other. Consequently, the more relevant the neighbors of a given node (i.e. the higher their activation levels) and the stronger the relationship between the node and its neighbors (i.e. the higher the weights of the links between them), the more relevant the node will be in the network. The spreading process is repeated until reaching all the nodes of the network. In the end, the highest activation levels correspond to the nodes that are most closely related to the initially selected ones. Since the spreading process permits to reach nodes that are not directly joined to the initially selected ones, SA techniques carry out inference processes where new knowledge is learned. To harness these inferential capabilities, several algorithms have been proposed for exploration and extraction of the most significant concepts formalized in a knowledge network. In i6 i8 p4 p5 i1 i i2 4 i5 i7 i3 p0 p1 p2 p3 i , i : instances belonging to class C 3 7 - join i , i 1 6 - join i,i 1 6 - join i , i 5 8 - join i,i 5 8 i1 i i2 4 i i3 5 p0 p1 p2 p3 Origin Terminus - path i , i 1 5 - path i,i 1 5 Property Sequence: ps [p , p , p , p ] 0123 Fig. 1. Semantic associations adopted in our reasoning-driven approach. Y. Blanco-Fernández et al. / Information Sciences xxx (2011) xxx–xxx 3 Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016
ARTICLE N PRESS Y. Blanco-Ferndndez et aL Information Sciences xcx(2011)xxx-xXx literature, many applications resort to the so-called Hopfield Net algorithm due to its beneficial properties of search and knowledge discovery, as explained in [ 23- 2. 2.1. The Hopfield Net algorithm iBe the Hopfield Net algorithm is based on a neural network that provides two capabilities especially relevant for the spread- ation by iteration)until e in e l1 the nodes of 12) for details ) On the one hand, the search capabilities allow the algo- levels of the remaining nodes in the network. On the other, the algorithm Hopfield Net traverses successively the nodes(iter heir activation levels converge to a stable value. The internals are as follows Firstly, a value 1 is assigned as the activation level for the initially activated nodes, and a value 0 is established for the remaining nodes of the network. ext, the initial activation levels are spread through the network, and the levels corresponding to all the nodes are com- puted by using the sigmoid function Us included in Eq (1)): A(+1)=5∑A(0)w),0≤j≤n-1 A(t+1)is the activation level of the node j in iteration t+ 1 A(t) is the activation level of the node i in iteration t. n is the number of nodes in the network, Wi is the weight of the link between the nodes i and j, being Wi=0 if there does not exist a link between them in the netwo where 0, is a configurable threshold, and 02 is a parameter used to modify the shape of the sigmoid function fs(x). The spreading process is repeated until the activation level of all the nodes reach a stable value, as indicated by Eq. (2), where s is a configurable parameter taking very low values (t+1)-A(D≤ 2. 2. Limitations of traditional Sa techniques in personalization field We have identified two severe drawbacks that prevent us from exploiting the inferential capabilities of traditional SA techniques in our reasoning-driven recommendation strategy. These drawbacks lie within()the kind of links modeled in the considered network and (ii) the weighting processes of those links. On the one hand, the kind of the modeled links is closely related to the richness of the reasoning processes carried out luring the spreading process. These links establish paths to propagate the relevance of the initially activated nodes to other nodes closely related to them. For that reason, it is possible that some significant nodes never be detected, due to the absence of links reaching them in the network. Existing SA techniques(see examples in 32, 35, 23, 37))model very simple relationships, which lead to poor inferences and prevent from discovering the knowledge hidden behind more complex associations. The second limitation of traditional Sa approaches is related to the weighting processes of the links modeled in the net work. According to the guidelines described in Section 2. 2, these weights remain invariable time. because their val- ues depend either on the existence of a relationship between the two linked nodes or on the strength of this relationship. This static weighting process is not appropriate for our personalization process, where it is necessary that the weights assigned to the links of the users network enable to: (1) learn automatically his her preferences from the feedback pro- vided after recommendations and (ii) adapt dynamically the spread-based inference process as these preferences evolve. In Section 4, we will explain how our reasoning-driven approach fights above limitations by extending traditional SA techniques so that they can be adopted in a content-based recommender system. Prior to that, the next section describes the procedures we have followed to formalize the domain ontology and to model the user profiles. 3. Background on our reasoning-driven personalization framewor 3.1. The domain ontology In the field of the Semantic Web, an ontology characterizes the concepts typical in a domain and their relationships by means of classes and properties, respectively, which are organized hierarchically [8]. Besides, the ontology is populated Please cite this article in press as: Y. Blanco-Fernandezet al, Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci.(2011). doi: 10.1016/jins2011.06.016
literature, many applications resort to the so-called Hopfield Net algorithm due to its beneficial properties of search and knowledge discovery, as explained in [23]. 2.2.1. The Hopfield Net algorithm The Hopfield Net algorithm is based on a neural network that provides two capabilities especially relevant for the spreading process: parallel search and convergence (see [12] for details). On the one hand, the search capabilities allow the algorithm to activate in each iteration all the nodes of the network in parallel, computing their activation levels according to the levels of the remaining nodes in the network. On the other, the algorithm Hopfield Net traverses successively the nodes (iteration by iteration) until their activation levels converge to a stable value. The internals are as follows: Firstly, a value 1 is assigned as the activation level for the initially activated nodes, and a value 0 is established for the remaining nodes of the network. Next, the initial activation levels are spread through the network, and the levels corresponding to all the nodes are computed by using the sigmoid function (fS included in Eq. (1)): Ajðt þ 1Þ ¼ fS Xn1 i¼0 AiðtÞ wij !; 0 6 j 6 n 1 ð1Þ In this expression: – Aj(t + 1) is the activation level of the node j in iteration t + 1, – Ai(t) is the activation level of the node i in iteration t, – n is the number of nodes in the network, – wij is the weight of the link between the nodes i and j, being wij = 0 if there does not exist a link between them in the network, – fSðxÞ ¼ 1 1þexp h1x h2 h i, where h1 is a configurable threshold, and h2 is a parameter used to modify the shape of the sigmoid function fS(x). The spreading process is repeated until the activation level of all the nodes reach a stable value, as indicated by Eq. (2), where n is a configurable parameter taking very low values Xn1 j¼0 jAjðt þ 1Þ AjðtÞj 6 n ð2Þ 2.2.2. Limitations of traditional SA techniques in personalization field We have identified two severe drawbacks that prevent us from exploiting the inferential capabilities of traditional SA techniques in our reasoning-driven recommendation strategy. These drawbacks lie within (i) the kind of links modeled in the considered network and (ii) the weighting processes of those links. On the one hand, the kind of the modeled links is closely related to the richness of the reasoning processes carried out during the spreading process. These links establish paths to propagate the relevance of the initially activated nodes to other nodes closely related to them. For that reason, it is possible that some significant nodes never be detected, due to the absence of links reaching them in the network. Existing SA techniques (see examples in [32,35,23,37]) model very simple relationships, which lead to poor inferences and prevent from discovering the knowledge hidden behind more complex associations. The second limitation of traditional SA approaches is related to the weighting processes of the links modeled in the network. According to the guidelines described in Section 2.2, these weights remain invariable over time, because their values depend either on the existence of a relationship between the two linked nodes or on the strength of this relationship. This static weighting process is not appropriate for our personalization process, where it is necessary that the weights assigned to the links of the user’s network enable to: (i) learn automatically his/her preferences from the feedback provided after recommendations and (ii) adapt dynamically the spread-based inference process as these preferences evolve. In Section 4, we will explain how our reasoning-driven approach fights above limitations by extending traditional SA techniques so that they can be adopted in a content-based recommender system. Prior to that, the next section describes the procedures we have followed to formalize the domain ontology and to model the user profiles. 3. Background on our reasoning-driven personalization framework 3.1. The domain ontology In the field of the Semantic Web, an ontology characterizes the concepts typical in a domain and their relationships by means of classes and properties, respectively, which are organized hierarchically [8]. Besides, the ontology is populated 4 Y. Blanco-Fernández et al. / Information Sciences xxx (2011) xxx–xxx Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016
ARTICLE N PRESS Y. Blanco-Fermandez et aL / Information Sciences xxx(2011)xXx-XXXx Sstancssff (hierarchical inks) Contents Cast away [1]IsAbout [2] HasActor [31 HasPlace [4]Has Period [5] Has Presenter [5] HasCRID East away a nurse Fig. 2. Subset of classes (top), properties and specific instances(bottom defined in an ontology about the tv domain. by including specific instances of classes and properties. In the context of a recommender system, class instances represent the available items and their attributes, whereas property instances link items and attributes to each other. We depict in Fig. 2 a brief excerpt from an ontology for the tv domain, defined from the Tv-Anytime specification(a collection of meta- data providing detailed descriptions about generic audiovisual contents 38 ). In this figure, it is possible to identify several class instances referred to specific TV programs, which belong to a hierarchy of genres(e. g. Fiction, Sports, Music, Leisure). The attributes of these Tv contents(e.g. cast, intented audience, topics) are also identified by hierarchically-organized classes and related to each program by means of labeled properties(eg. hasActor, hasIntendedAudience, isAbout). Ontologies have become the cornerstone of the Semantic Web due to two reasons. On the one hand, formal conceptual- izations enable inference processes to discover new knowledge from the represented information On the other, ontologies facilitate automated knowledge sharing, by allowing easy reuse between users and software agents. This feature facilitates the development of ontologies, which would be a tedious task otherwise. Nowadays, there exist repositories containing mu tiple and very diverse ontologies (e.g. SchemaWeb). as well as numerous management tools providing useful functionalities for development tasks(e.g. merging of multiple ontologies, consistency checking, discovery of equivalent classes, reuse of con- cept descriptions, automatic categorization of instances in the appropriate classes via logics-based reasoners [ 3, 17]. etc ) In sum, by reusing the concepts and relationships formalized in publicly available ontologies and resorting to the existing man- gement tools, it is possible to create a domain ontology for reasoning-purposes with acceptable effort. There exist several standard implementation languages for ontology development. The first proposals were RDF [7 and RDFS [10, which added a formal semantics to the purely syntactic specifications provided in XML Next, DAML [15] and OIL 18 arose, which have been finally fused and standardized by w3C as OWL [26]. the most expressive language nowadays including three sub-levels(Lite, DL and Full). The language to use in pends on the knowledge and expressiveness necessities of the domain he application of our reasoning-driven approach de- der system. IAvailableinhttp://www.schemaweb.info/schema/browseschemaaspx. Please cite this article in press as:Y. Blanco-Fernandez et al, Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci.(2011). doi: 10.1016)jins2011.06.016
by including specific instances of classes and properties. In the context of a recommender system, class instances represent the available items and their attributes, whereas property instances link items and attributes to each other. We depict in Fig. 2 a brief excerpt from an ontology for the TV domain, defined from the TV-Anytime specification (a collection of metadata providing detailed descriptions about generic audiovisual contents [38]). In this figure, it is possible to identify several class instances referred to specific TV programs, which belong to a hierarchy of genres (e.g. Fiction, Sports, Music, Leisure). The attributes of these TV contents (e.g. cast, intented audience, topics) are also identified by hierarchically-organized classes, and related to each program by means of labeled properties (e.g. hasActor, hasIntendedAudience, isAbout). Ontologies have become the cornerstone of the Semantic Web due to two reasons. On the one hand, formal conceptualizations enable inference processes to discover new knowledge from the represented information. On the other, ontologies facilitate automated knowledge sharing, by allowing easy reuse between users and software agents. This feature facilitates the development of ontologies, which would be a tedious task otherwise. Nowadays, there exist repositories containing multiple and very diverse ontologies (e.g. SchemaWeb1 ), as well as numerous management tools providing useful functionalities for development tasks (e.g. merging of multiple ontologies, consistency checking, discovery of equivalent classes, reuse of concept descriptions, automatic categorization of instances in the appropriate classes via logics-based reasoners [3,17], etc.). In sum, by reusing the concepts and relationships formalized in publicly available ontologies and resorting to the existing management tools, it is possible to create a domain ontology for reasoning-purposes with acceptable effort. There exist several standard implementation languages for ontology development. The first proposals were RDF [7] and RDFS [10], which added a formal semantics to the purely syntactic specifications provided in XML. Next, DAML [15] and OIL [18] arose, which have been finally fused and standardized by W3C as OWL [26], the most expressive language nowadays including three sub-levels (Lite, DL and Full). The language to use in the application of our reasoning-driven approach depends on the knowledge and expressiveness necessities of the domain considered and the recommender system. [6] Properties BBC breaking news CRID1 CRID2 CRID4 CRID6 CRID7 CRID8 CRID15 CRID14 CRID16 CRID11 CRID10 CRID13 CRID12 CRID5 CRID3 Darren Gordon [5] Hamlet Braveheart Renaissance T enice Michelangelo’s David Sculpture Renaissance sculpture want New York Inside Sydney T New York Sydney Delhi The ceramics Ceramics Indian culinary specialties Bombay Hamlet Cooking Hell’s kitchen stove [6] [6] [6] [6] [6] [6] [6] [6] [6] [6] [6] [6] [1] [1] [1] [1] [1] [1] [2] [2] [2] [6] [3] [3] [4] [3] [2] [2] [6] [1] [1] [1] [2] Varanasi CRID17 [6] [3] [3] Cast Away Indian culinary specialties BBC breaking news Inside New York Sydney T stove Tourism Cookery Leisure Contents Fiction Contents Contents TV Contents Sculpture Ceramics India cities InstanceOf Varanasi Delhi Bombay Romance Drama Action Ceramics Sculpture News Cultural Arts Reality Shows USA cities New York Australia cities Sydney want enice ceramics Renaissance sculpture Michelangelo’s David Hell’s kitchen Hamlet Braveheart Fig. 2. Subset of classes (top), properties and specific instances (bottom) defined in an ontology about the TV domain. 1 Available in http://www.schemaweb.info/schema/BrowseSchema.aspx. Y. Blanco-Fernández et al. / Information Sciences xxx (2011) xxx–xxx 5 Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016
ARTICLE N PRESS Y. Blanco-Ferndndez et aL Information Sciences xcx(2011)xxx-xXx Reasoning about a user's preferences requires a formal representation including semantic descriptions of the items that are appealing or unappealing to him/ her (named positive and negative preferences, respectively). These descriptions permit a recommender system to learn new knowledge about the user's interests, which is not possible with many of the existing user Some existing works define too simple user models, containing only flat lists of key words(e.g attributes) or ratings referred to each item defined in the users profile [11, 24, 39. These proposals provide little knowledge about the users references, and therefore hamper the application of advanced reasoning processes. Other more sophisticated proposals take advantage of the hierarchical structures defined in an ontology to model the ers preferences 27, 42, 19 In these works, profiles do not contain the specific items the user(dis)liked in but the classes under which these items are categorized in a hierarchy. The main drawback of this approach is ti explores the hierarchical structure of the domain and misses the semantic descriptions of the items, which are es useful for user modeling tasks and for subsequent reasoning processes, as we will describe through the paper. Bearing in mind that the descriptions required in our reasoning mechanisms are already defined in the domain ontology, we propose to model the users preferences by reusing the knowledge formalized in it. The resulting models are named ontology profiles and store the interest of the user in: (i) the attributes of the items which are(un ) interesting for him/ her and(ii)the hier archy of classes under which these items are categorized. This approach has two main advantages for a recommender system On the one hand, the formal representation of the user's profile allows the system to reason and compare effectively his/ her preferences against the available items, thus favoring more accurate personalization processe On the other hand, we provide the system with a very detailed model of the users interests, while not requiring that the classes, properties and instances that identify these preferences be stored in each profile. Thus, we significantly reduce the storage capabilities needed in the reasoning-driven recommender system. To this aim, we use the domain ontology as a common knowledge repository, keeping only two elements in the users profile: unique references(denoted by IDs) Profile P Pre DOI indexes index Instances in the domain ontolog in the FICTIO Fig. 3. Our ontology-based approach for modeling user in a TV recommender system. Please cite this article in press as: Y.Blanco-Fernandezet al, Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci.(2011). doi: 10.1016/jins2011.06.016
3.2. User modeling technique Reasoning about a user’s preferences requires a formal representation including semantic descriptions of the items that are appealing or unappealing to him/her (named positive and negative preferences, respectively). These descriptions permit a recommender system to learn new knowledge about the user’s interests, which is not possible with many of the existing user modeling techniques: Some existing works define too simple user models, containing only flat lists of key words (e.g. attributes) or ratings referred to each item defined in the user’s profile [11,24,39]. These proposals provide little knowledge about the user’s preferences, and therefore hamper the application of advanced reasoning processes. Other more sophisticated proposals take advantage of the hierarchical structures defined in an ontology to model the user’s preferences [27,42,19]. In these works, profiles do not contain the specific items the user (dis)liked in the past, but the classes under which these items are categorized in a hierarchy. The main drawback of this approach is that it only explores the hierarchical structure of the domain and misses the semantic descriptions of the items, which are especially useful for user modeling tasks and for subsequent reasoning processes, as we will describe through the paper. Bearing in mind that the descriptions required in our reasoning mechanisms are already defined in the domain ontology, we propose to model the user’s preferences by reusing the knowledge formalized in it. The resulting models are named ontologyprofiles and store the interest of the user in: (i) the attributes of the items which are (un)interesting for him/her and (ii) the hierarchy of classes under which these items are categorized. This approach has two main advantages for a recommender system: On the one hand, the formal representation of the user’s profile allows the system to reason and compare effectively his/ her preferences against the available items, thus favoring more accurate personalization processes. On the other hand, we provide the system with a very detailed model of the user’s interests, while not requiring that the classes, properties and instances that identify these preferences be stored in each profile. Thus, we significantly reduce the storage capabilities needed in the reasoning-driven recommender system. To this aim, we use the domain ontology as a common knowledge repository, keeping only two elements in the user’s profile: unique references (denoted by IDs) ID1 ID3 DOI indexes DOI indexes DOI indexes DOI indexes ID1 ID2 X Y ID3 ID2 ID1 Actor Director Alert Topic Intended Audience FICTION Drama Cookery Adventure Tourism Gardening LEISURE TV CONTENTS InstanceOf SubClassOf Properties Fig. 3. Our ontology-based approach for modeling user in a TV recommender system. 6 Y. Blanco-Fernández et al. / Information Sciences xxx (2011) xxx–xxx Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016
ARTICLE N PRESS Y. Blanco-Fermandez et aL / Information Sciences xxx(2011)xXx-XXXx that identify the items the user(dis)liked and his/her specific level of interest in each one of them. These references pe mit to locate in the ontology the items defined in the user's profile and to query their semantic descriptions (ie attributes and hierarchical classes )over the conceptualization, as shown in Fig 3 for a recommender system in Tv domain. Note that our modeling technique does not consider a flat list of attributes referred to the users preferences, but rather it xploits the structure of the domain ontology and the relationships existing among these attributes in order to learn knowl- edge about his/her interests and exploit it during the personalization process. bviously, recommender systems require the users to define some initial preferences to start working. Considering the users'involvement, the goal is to provide a user-friendly interface to alleviate their initialization burden. Our user modeling technique exploits the hierarchical structure of the underlying ontology for that purpose. Specifically, a list of classes/sub- classes and specific instances referred to the items to be recommended(eg. programs in the tv domain)is shown to the user, who can identify his/ her positive and negative preferences by assigning ratings to each specific item. The hierarchy of classes displayed is self-explanatory (see bottom of Fig. 3), so that the users can easily browse it and feel free to rate as items as they wan After the profile initialization, it is necessary to measure the users level of interest in each item included in his/her profile. To this aim, we have defined the so-called Dol indexes( Degree of Interest)in the range [-1. 1 ], with -1 representing the greatest disliking and 1 the greatest liking. These indexes can be either explicitly entered by the user or inferred automat- ically by the recommender system from the relevance feedback provided after recommendations. The dol index computed for each item is also used to set the ratings corresponding to its attributes and to the classes under which the item is cate- gorized in the ontology. Specifically, the dol of an attribute is taken as the average of the dols of the items it is linked to Similarly, the dols of the most specific classes are computed as the average of the dols of the items classified under them. Then, we propagate these values upwards in the hierarchy until reaching its root class. For that purpose, we adopt the ap- proposed in[42], which leads to higher Dol indexes for the superclasses closer to the leaf class whose value is being gated, and lower ones for the classes which are closer to the root of the hierarchy. Besides, the higher the dol of a given nd the lower its number of siblings, the higher the value propagated to its superclass 4. Using content-based filtering in tandem with Sa techniques As we mentioned in the introduction, our content-based strategy is divided into two phases named pre-filtering and rec- emendation phase. Even though the pre-filtering phase has been detailed in 9]. in this section we summarize the main as- ects of this process with the goal of clarifying how the user's Ontology of Interest is selected( Section 4. 1)and how it is processed by Sa techniques in the recommendation phase of the strategy( Sections 4.2, 4.3, 4.4). Regarding SA techniques. we extend traditional approaches by overcoming the limitations pointed out in Section 2. 2. 2, which hamper their adoption in a recommender system where the focus must be put on the user's preferences: On the one hand, our approach extends the simple relationships considered by traditional Sa techniques by considering both the properties defined in the ontology and the semantic associations inferred from them. this rich variety of rela- ionships permit to establish links that propagate the relevance of the items selected by the pre-filtering phase, leading to diverse enhanced recommendations On the other hand, to fulfill the personalization requirements of a recommender system, our link weighting process does not depend only on the two nodes joined by the considered link, but also on the strength of) their relationship to the items defined in the user's profile This way, the links of the network created for the user are updated as our strategy learns new knowledge about his her preferences, thus leading to tailor-made recommendations after the spreading process. Once the principles of our SA approach have been sketched, we focus on the processes required for its use in our content based strategy: (i) selection of the user's Ontology of Interest. (ii)creation of the users SA network, (ii )weighting of its links, (iii) processing of the network by Sa techniques, and(iv) selection of our reasoning-based recomm 4.1. Pre-filtering phase: creating the user's Ontology of Interest Our pre-filtering phase decides which instances of classes and properties from the domain ontology must be included in the users Ontology of Interest because they are relevant for him/her. For that purpose, we firstly locate in the domain ontol- ntil rePealing to the user(defined in his her profile). Next, we traverse successively the properties bound to these items until reaching new class instances in the ontology, referred to other items and their attributes. In order to guarantee computational feasibility, we have developed a controlled inference mechanism that progressively filters the instances of classes and properties that do not provide useful knowledge for the personalization process As new nodes are reached from a given e, we firstly quantify their relevance for the user by an index named seman- tic intensity(denoted by isem(n) for node n) whose computation process will be described in this section cite this article in press as: Y. Blanco-Fernandez et al, Exploring synergies between content-based filtering and Spreading Activation iques in knowledge-based recommender systems, Inform. Sci. (2011). doi: 10. 1016/j ins. 2011.06.016
that identify the items the user (dis)liked, and his/her specific level of interest in each one of them. These references permit to locate in the ontology the items defined in the user’s profile and to query their semantic descriptions (i.e. attributes and hierarchical classes) over the conceptualization, as shown in Fig. 3 for a recommender system in TV domain. Note that our modeling technique does not consider a flat list of attributes referred to the user’s preferences, but rather it exploits the structure of the domain ontology and the relationships existing among these attributes in order to learn knowledge about his/her interests and exploit it during the personalization process. Obviously, recommender systems require the users to define some initial preferences to start working. Considering the users’ involvement, the goal is to provide a user-friendly interface to alleviate their initialization burden. Our user modeling technique exploits the hierarchical structure of the underlying ontology for that purpose. Specifically, a list of classes/subclasses and specific instances referred to the items to be recommended (e.g. programs in the TV domain) is shown to the user, who can identify his/her positive and negative preferences by assigning ratings to each specific item. The hierarchy of classes displayed is self-explanatory (see bottom of Fig. 3), so that the users can easily browse it and feel free to rate as items as they want. After the profile initialization, it is necessary to measure the user’s level of interest in each item included in his/her profile. To this aim, we have defined the so-called DOI indexes (Degree Of Interest) in the range [1,1], with 1 representing the greatest disliking and 1 the greatest liking. These indexes can be either explicitly entered by the user or inferred automatically by the recommender system from the relevance feedback provided after recommendations. The DOI index computed for each item is also used to set the ratings corresponding to its attributes and to the classes under which the item is categorized in the ontology. Specifically, the DOI of an attribute is taken as the average of the DOIs of the items it is linked to. Similarly, the DOIs of the most specific classes are computed as the average of the DOIs of the items classified under them. Then, we propagate these values upwards in the hierarchy until reaching its root class. For that purpose, we adopt the approach proposed in [42], which leads to higher DOI indexes for the superclasses closer to the leaf class whose value is being propagated, and lower ones for the classes which are closer to the root of the hierarchy. Besides, the higher the DOI of a given class and the lower its number of siblings, the higher the value propagated to its superclass. 4. Using content-based filtering in tandem with SA techniques As we mentioned in the introduction, our content-based strategy is divided into two phases named pre-filtering and recommendation phase. Even though the pre-filtering phase has been detailed in [9], in this section we summarize the main aspects of this process with the goal of clarifying how the user’s Ontology of Interest is selected (Section 4.1) and how it is processed by SA techniques in the recommendation phase of the strategy (Sections 4.2, 4.3, 4.4). Regarding SA techniques, we extend traditional approaches by overcoming the limitations pointed out in Section 2.2.2, which hamper their adoption in a recommender system where the focus must be put on the user’s preferences: On the one hand, our approach extends the simple relationships considered by traditional SA techniques by considering both the properties defined in the ontology and the semantic associations inferred from them. This rich variety of relationships permit to establish links that propagate the relevance of the items selected by the pre-filtering phase, leading to diverse enhanced recommendations. On the other hand, to fulfill the personalization requirements of a recommender system, our link weighting process does not depend only on the two nodes joined by the considered link, but also on (the strength of) their relationship to the items defined in the user’s profile. This way, the links of the network created for the user are updated as our strategy learns new knowledge about his/her preferences, thus leading to tailor-made recommendations after the spreading process. Once the principles of our SA approach have been sketched, we focus on the processes required for its use in our contentbased strategy: (i) selection of the user’s Ontology of Interest, (ii) creation of the user’s SA network, (ii) weighting of its links, (iii) processing of the network by SA techniques, and (iv) selection of our reasoning-based recommendations. 4.1. Pre-filtering phase: creating the user’s Ontology of Interest Our pre-filtering phase decides which instances of classes and properties from the domain ontology must be included in the user’s Ontology of Interest because they are relevant for him/her. For that purpose, we firstly locate in the domain ontology the items that are (un)appealing to the user (defined in his/her profile). Next, we traverse successively the properties bound to these items until reaching new class instances in the ontology, referred to other items and their attributes. In order to guarantee computational feasibility, we have developed a controlled inference mechanism that progressively filters the instances of classes and properties that do not provide useful knowledge for the personalization process: As new nodes are reached from a given instance, we firstly quantify their relevance for the user by an index named semantic intensity (denoted by kSem(n) for node n), whose computation process will be described in this section. Y. Blanco-Fernández et al. / Information Sciences xxx (2011) xxx–xxx 7 Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016
ARTICLE N PRESS Y. Blanco-Ferndndez et aL Information Sciences xcx(2011)xxx-xXx Next, the nodes whose intensity indexes are not greater than a specific threshold are disregarded so that our inference mechanism continues traversing only the properties that permit to reach new nodes from those that are relevant for the In order to measure the semantic intensity of a node n, we take into account various ontology-dependent pre-filtering cri- the more significant the relationship between a given node and the user's preferences, the higher the resulting value. Some of these criteria(described in detail in 9]) are summarized next (1)Length of the property sequence that enables to reach the node starting from the user's preferences. The longer this sequence, the lower the semantic intensity of the node because its relationship to the users preferences is less signif- icant due to the presence of many intermediate nodes. (2) Existence of hierarchical relationships between the node and the users preferences. The intensity of a node increases when it is possible to find a common ancestor between it and the user's preferences in the hierarchies defined in the (3)Existence of implicit relationships between the node and the user's preferences detected by graph theory betweenness. In graph theory [16], the betweenness among three nodes is high when in the most of paths from the first node to the second one, the third node is also included. therefore, from a high value of betweenness, it follows that the involved nodes are strongly related. In our approach, these nodes are the user's preferences and the class instance whose relevance is being measured Once the nodes related to the user's preferences (and also the properties linking them to each other) have been selected our strategy infers semantic associations between the instances referred to items that can be recommended. As per the cat egorization of semantic associations described in Section 2. 1, we detect the following relationships between the items de- fined in the users Ontology of Interest First, p-path associations between the items that are joined by a property sequence in the Ontology of Interest, as it hap- ns with the programs Hell,s kitchen and Indian culinary specialties in Fig. 2, which are linked by the instance cooking in the ontology. Second, p-join associations between, for instance, the items whose attributes belong to a union class in the ontology. As an example, the programs Renaissance sculpture and The Art of ceramics in Fig. 2 are associated because both are about plastic arts strongly related to each other(as shown in the class hierarchy of the figure, sculpture and ceramics belong to the union class Plastic arts ). Starting from the user's Ontology of Interest and the semantic associations inferred among its nodes, we create the user's SA network, whose knowledge is explored during the second phase of the strategy by exploiting the inference capabilities provided by Sa techniques. 4.2. Creation of the user's SA network The user's Sa network can be easily built starting from his /her Ontology of Interest. Specifically, the nodes of this network are the class instances selected by the pre-filtering phase of our strategy. The knowledge learned in this first phase also helps to identify the links that relate the nodes to each other, which permit to carry out the inference processes toward recomm dations. In this regard, our SA approach defines two kind of links Real links. These links model the knowledge that is explicitly represented in the user's Ontology of Interest. Specifically, we consider a real link in the user's SA network for each one of the property instances included in his/her Ontology Virtual links. These links refer to relationships inferred from the Ontology of Interest. In this group, we include both simple hierarchical relationships and the complex semantic associations discovered from the properties and hierarchical links of he users Ontology of Interest. According to the nature of both relationships we identify two kind of virtual links: Associative virtual links. We consider an associative virtual link between each pair of items related by p-path or p-join associations. For instance, from the associations depicted in Fig. 1, we define three associative virtual links: between items i1 and is, due to the p-path association: between items in and i6. due to p-join; and between items is and ig, again due to p-join. Hierarchical virtual links We consider a hierarchical virtual link en the two instances belonging to the union class that causes p-join associations. For instance, in Fig. 1 it is possible to establish a virtual link between items i3 and i7, which are classified under the union class c We define a new type of structure(named virt arting from p-join associations existing between two Items This structure permits to go from one item to by crossing a minimum number of real links and the hierarchical link that originates the p-join association between items. The length of the virtual path is defined as the links contained in it. As an example, in Fig. 1 it is possible to find a virtual path(of length 3)between items in and i6, which Please cite this article in press as: Y. Blanco-Fernandezet al, Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci.(2011). doi: 10.1016/jins2011.06.016
Next, the nodes whose intensity indexes are not greater than a specific threshold are disregarded, so that our inference mechanism continues traversing only the properties that permit to reach new nodes from those that are relevant for the user. In order to measure the semantic intensity of a node n, we take into account various ontology-dependent pre-filtering criteria, so that the more significant the relationship between a given node and the user’s preferences, the higher the resulting value. Some of these criteria (described in detail in [9]) are summarized next: (1) Length of the property sequence that enables to reach the node starting from the user’s preferences. The longer this sequence, the lower the semantic intensity of the node because its relationship to the user’s preferences is less significant due to the presence of many intermediate nodes. (2) Existence of hierarchical relationships between the node and the user’s preferences. The intensity of a node increases when it is possible to find a common ancestor between it and the user’s preferences in the hierarchies defined in the ontology. (3) Existence of implicit relationships between the node and the user’s preferences detected by graph theory betweenness. In graph theory [16], the betweenness among three nodes is high when in the most of paths from the first node to the second one, the third node is also included. Therefore, from a high value of betweenness, it follows that the involved nodes are strongly related. In our approach, these nodes are the user’s preferences and the class instance whose relevance is being measured. Once the nodes related to the user’s preferences (and also the properties linking them to each other) have been selected, our strategy infers semantic associations between the instances referred to items that can be recommended. As per the categorization of semantic associations described in Section 2.1, we detect the following relationships between the items de- fined in the user’s Ontology of Interest: First, q-path associations between the items that are joined by a property sequence in the Ontology of Interest, as it happens with the programs Hell’s kitchen and Indian culinary specialties in Fig. 2, which are linked by the instance cooking in the ontology. Second, q-join associations between, for instance, the items whose attributes belong to a union class in the ontology. As an example, the programs Renaissance sculpture and The Art of ceramics in Fig. 2 are associated because both are about plastic arts strongly related to each other (as shown in the class hierarchy of the figure, sculpture and ceramics belong to the union class Plastic arts). Starting from the user’s Ontology of Interest and the semantic associations inferred among its nodes, we create the user’s SA network, whose knowledge is explored during the second phase of the strategy by exploiting the inference capabilities provided by SA techniques. 4.2. Creation of the user’s SA network The user’s SA network can be easily built starting from his/her Ontology of Interest. Specifically, the nodes of this network are the class instances selected by the pre-filtering phase of our strategy. The knowledge learned in this first phase also helps to identify the links that relate the nodes to each other, which permit to carry out the inference processes toward recommendations. In this regard, our SA approach defines two kind of links: Real links. These links model the knowledge that is explicitly represented in the user’s Ontology of Interest. Specifically, we consider a real link in the user’s SA network for each one of the property instances included in his/her Ontology. Virtual links. These links refer to relationships inferred from the Ontology of Interest. In this group, we include both simple hierarchical relationships and the complex semantic associations discovered from the properties and hierarchical links of the user’s Ontology of Interest. According to the nature of both relationships, we identify two kind of virtual links: – Associative virtual links. We consider an associative virtual link between each pair of items related by q-path or q-join associations. For instance, from the associations depicted in Fig. 1, we define three associative virtual links: between items i1 and i5, due to the q-path association; between items i1 and i6, due to q-join; and between items i5 and i8, again due to q-join. – Hierarchical virtual links. We consider a hierarchical virtual link between the two instances belonging to the union class that causes q-join associations. For instance, in Fig. 1 it is possible to establish a virtual link between items i3 and i7, which are classified under the union class C. We define a new type of structure (named virtual path) starting from q-join associations existing between two specific items. This structure permits to go from one item to the other by crossing a minimum number of real links and the hierarchical link that originates the q-join association between the two items. The length of the virtual path is defined as the number of real links contained in it. As an example, in Fig. 1 it is possible to find a virtual path (of length 3) between items i1 and i6, which 8 Y. Blanco-Fernández et al. / Information Sciences xxx (2011) xxx–xxx Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016
ARTICLE N PRESS Y. Blanco-Fermandez et aL / Information Sciences xxx(2011)xXx-XXXx consists of the real links 11-12, i2-13, i7-i6 and the hierarchical link i3-1z. Analogously to what happens with property sequences, the shorter a virtual path between two items, the more relevant their relationship will be. due to the presence of few intermediate nodes between them 4.3. Weighing links in the user's SA network As we explained previously, incorporating the personalization requirements of our recommendation strategy into classic Sa techniques requires to adapt the weighing process of the links modeled in the users Sa network. Instead of considering that the weight of a link between two nodes depends only on the strength of their mutual relationship, our approach im- poses two constraints on the links to be weighed: First, given two nodes joined by a link, we consider that the stronger the(semantic)relationship between the two linked nodes and the user's preferences, the higher the weight of the link. Second, the weights are dynamically adjusted as the users preferences evolve over time, thus offering permanently updated content-based recommendations. In our approach, the weight of the links are assigned by combining two parameters: (i) the contribution of the two linked des, measured by their respective relevance functions and (ii)the type of link considered. 4.3. 1. Relevance function of a node The aim of the relevance function of a node in the Sa network is to quantify its importance for the user, by considering is/her personal preferences and the knowledge learned from his/her Ontology of Interest. Eq. 3)shows how we compute the value of the relevance function for the node i which is linked to the node j(denoted by f() f(= DOlu() if i is defined in Us profile isem(i otherwise If the node i is defined in the user Us profile, the value of its relevance function f()is its level of interest DOlu(i), since this is the most appropriate indicator to measure how relevant the node i is for the target user. Otherwise, f(i)equals the value of the semantic intensity of the node i, so that the higher isem(i), the most significant the relationship between i and the users preferences, and therefore, the more relevant the node i is for him/ her(remember Section 4.1). 4.3. 2 Type of link to be weighed The weights assigned to the virtual links are lower than those set for the real links. The intuition behind this idea is that the relationship existing between two nodes joined by a real link is explicitly represented in the user Ontology of Interest by means of properties, while the relationship between two nodes joined by a virtual link has been inferred by a reasoning-driven prediction process. Thus, as established by Eg.(4). the weight of the link between nodes i and j is computed by combining an attenuation factor Ay E[0, 1)with the relevance values of both 0.5·(0)+f() In case of real link ).5.Hi (i0)+J()in case of virtual link As shown in Eq (5), the value of the factor Hi depends on the kind of virtual link established between nodes i and j Specif ically, the weights of the hierarchical virtual links are reduced by a factor 0.85 that prevents the contribution of these links he contrary, the value of piy for the associative of the semantic association inferred between the two linked nodes, so that the stronger the relationship between i and j, the higher the value of pi. Specifically, we consider that the closer two nodes in the user's SA network, the stronger the association between them. The distance metric defined in our approach depends on the type of association inferred between the two linked ms(i and j) In case of a p-path association, we use the length of the property sequence between i and j (length(ps)in Eq (5))in order to measure the strength of the relationship. The higher the length of the sequence, the less significant the association and, therefore, the more severe the attenuation of the weight corresponding to the associative link between the two joined In case of a p-join association, we use the length of the virtual path existing between nodes i and j(length(vpath)) in Eq (5) 2 The value 0.85 has been empirically adjusted after numerous experiments. Please cite this article in press as:Y. Blanco-Fernandez et al, Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci.(2011). doi: 10.1016)jins2011.06.016
consists of the real links i1–i2, i2–i3, i7–i6 and the hierarchical link i3–i7. Analogously to what happens with property sequences, the shorter a virtual path between two items, the more relevant their relationship will be, due to the presence of few intermediate nodes between them. 4.3. Weighing links in the user’s SA network As we explained previously, incorporating the personalization requirements of our recommendation strategy into classic SA techniques requires to adapt the weighing process of the links modeled in the user’s SA network. Instead of considering that the weight of a link between two nodes depends only on the strength of their mutual relationship, our approach imposes two constraints on the links to be weighed: First, given two nodes joined by a link, we consider that the stronger the (semantic) relationship between the two linked nodes and the user’s preferences, the higher the weight of the link. Second, the weights are dynamically adjusted as the user’s preferences evolve over time, thus offering permanently updated content-based recommendations. In our approach, the weight of the links are assigned by combining two parameters: (i) the contribution of the two linked nodes, measured by their respective relevance functions and (ii) the type of link considered. 4.3.1. Relevance function of a node The aim of the relevance function of a node in the SA network is to quantify its importance for the user, by considering his/her personal preferences and the knowledge learned from his/her Ontology of Interest. Eq. (3) shows how we compute the value of the relevance function for the node i which is linked to the node j (denoted by fj(i)): fjðiÞ ¼ DOIUðiÞ if i is defined in U’s profile kSemðiÞ otherwise ð3Þ If the node i is defined in the user U’s profile, the value of its relevance function fj(i) is its level of interest DOIU(i), since this is the most appropriate indicator to measure how relevant the node i is for the target user. Otherwise, fj(i) equals the value of the semantic intensity of the node i, so that the higher kSem(i), the most significant the relationship between i and the user’s preferences, and therefore, the more relevant the node i is for him/her (remember Section 4.1). 4.3.2. Type of link to be weighed The weights assigned to the virtual links are lower than those set for the real links. The intuition behind this idea is that the relationship existing between two nodes joined by a real link is explicitly represented in the user’s Ontology of Interest by means of properties, while the relationship between two nodes joined by a virtual link has been inferred by a reasoning-driven prediction process. Thus, as established by Eq. (4), the weight of the link between nodes i and j is computed by combining an attenuation factor lij 2 [0,1) with the relevance values of both nodes. wij ¼ wji ¼ 0:5 ðfiðjÞ þ fjðiÞÞ in case of real link 0:5 lij ðfiðjÞ þ fjðiÞÞ in case of virtual link ( ð4Þ As shown in Eq. (5), the value of the factor lij depends on the kind of virtual link established between nodes i and j. Specifically, the weights of the hierarchical virtual links are reduced by a factor 0.85 that prevents the contribution of these links from suffering an excessive decrease.2 On the contrary, the value of lij for the associative virtual links depends on the relevance of the semantic association inferred between the two linked nodes, so that the stronger the relationship between i and j, the higher the value of lij. Specifically, we consider that the closer two nodes in the user’s SA network, the stronger the association between them. The distance metric defined in our approach depends on the type of association inferred between the two linked items (i and j): In case of a q-path association, we use the length of the property sequence between i and j (length(ps) in Eq. (5)) in order to measure the strength of the relationship. The higher the length of the sequence, the less significant the association and, therefore, the more severe the attenuation of the weight corresponding to the associative link between the two joined nodes. In case of a q-join association, we use the length of the virtual path existing between nodes i and j (length(vpath)), as shown in Eq. (5). 2 The value 0.85 has been empirically adjusted after numerous experiments. Y. Blanco-Fernández et al. / Information Sciences xxx (2011) xxx–xxx 9 Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016
ARTICLE N PRESS Y. Blanco-Ferndndez et aL Information Sciences xcx(2011)xxx-xXx 0.85 for hierarchical virtual link A for associative virtual link Ay -= length(ps)th if p- path From our weighting process, it follows that the weight of an associative virtual link between two nodes depends both on heir relevance for the user just like in real links and hierarchical virtual links) and on the kind of semantic associations in- ferred between both nodes. These two contributions permit to differentiate our personalization approach from other existing Sa proposals where there is no place for complex relationships. 4.4. The processes of spreading activation and selection of recommendations Once the knowledge learned about the users preferences has been modeled in his /her SA network, we process the seman- tics of its nodes and links by an improved spreading activation mechanism Firstly, we activate in the user's SA network the nodes referred to the items defined in his/her profile, considering botl his/her positive and negative preferences. The positive preferences permit the spreading process to identify items that are significant for the user, because they are related to items he/she enjoyed in the past. The negative preferences lead to detect items that must not be suggested due to their relationships to unappealing items. Secondly we assign the activation levels of all the nodes in the network. we use the dol indexes defined in the users profile for the nodes initially activated, and a value 0 for the remaining nodes. Next, the activation levels of the users preferences are propagated through the Sa network by using the Hopfield Net algo- rithm, which is in charge of selecting the items with high levels to be recommended to the user. The principle of parallel arch of this algorithm is especially beneficial for our personalization approach, because the capability of activating in parallel all the nodes in the user's Sa network permits to carry out the spreading process in an efficient way specifically the algorithm computes the activation level of each node in the user's sa network by adding the contribution from all of its neighbor nodes. This contribution considers both the activation level of each neighbor node and the weight of the link (real or virtual)joining it to the considered node For that reason, the more relevant the neighbors of a node (i.e. the higher activation levels) and the stronger the relationships among them and the considered node (i.e. the greater weights of links ) the more significant this node will be for the user. This contribution is incorporated as an argument into the sigmoid function used by Hopfield Net(see Eq (1)). As shown in Eq (3). the weight of a link is computed starting from either the dol indexes of the two joined nodes(if they are defined in the user's profile)or from their semantic intensity values(otherwise). Consequently, it holds that The sigmoid function measures the highest activation values for nodes which are connected both to class instances very appealing to the user ( whose Dol indexes are very significant), and to nodes greatly related to his/her positive IS Analogously, according to the internals of our content-based strategy, the sigmoid function quantifies low activation levels for class instances which are related to the users' negative preferences, thus preventing from suggesting these Finally, our strategy selects the items to be suggested to the user. Specifically, the strategy recommends only the items of the users SA network whose activation level is greater than a configurable threshold 5. This parameter is clearly dependent on the application domain and the recommender system that adopts our strategy. Anyway, the values must be always very high(close to 1 )to guarantee that the items suggested are closely related to the user's preferences 3 5. A sample scenario The research work of our content-based recommendation strategy has been tested in the scope of a Tv recommender sys- ers that broadcasts daily 43 TV channels. The goal of this system is to identify potentially appealing programs to each subscriber among the contents available in the digital stream. In this section, we illustrate how to select the Tv programs that are most appealing to a user by considering the knowledge formalized in the excerpt from the tv ontology depicted in Fig. 2. Even though this ontology contains a reduced number of classes, properties and instances, it serves to highlight the differences between our reasoning-based recommendations and those offered by traditional (syntactic) content-based approaches Assume a Tv viewer U whose positive and negative preferences are shown in Table 1, including the Tv programs U liked and disliked in the past, his/her dOI indexes (in brackets ), and the classes under which these programs are catego- rized in the hierarchy of genres defined in the tv ontology used the parameters 61=10, 62=0.8 and 4=0.0s(for the Hopfield Net algorithm), and recommendation thresholds 8 in the range [0.78,0.9] in the tests carried out in the Digital TV field. Please cite this article in press as: Y.Blanco-Fernandezet al, Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci.(2011). doi: 10.1016/jins2011.06.016
lij ¼ 0:85 for hierarchical virtual link 1 l^ij for associative virtual link ( l^ij ¼ lengthðpsÞ if q pathði; jÞ lengthðvpathÞ if q joinði; jÞ ð5Þ From our weighting process, it follows that the weight of an associative virtual link between two nodes depends both on their relevance for the user (just like in real links and hierarchical virtual links) and on the kind of semantic associations inferred between both nodes. These two contributions permit to differentiate our personalization approach from other existing SA proposals where there is no place for complex relationships. 4.4. The processes of spreading activation and selection of recommendations Once the knowledge learned about the user’s preferences has been modeled in his/her SA network, we process the semantics of its nodes and links by an improved spreading activation mechanism: Firstly, we activate in the user’s SA network the nodes referred to the items defined in his/her profile, considering both his/her positive and negative preferences. The positive preferences permit the spreading process to identify items that are significant for the user, because they are related to items he/she enjoyed in the past. The negative preferences lead to detect items that must not be suggested due to their relationships to unappealing items. Secondly, we assign the activation levels of all the nodes in the network. We use the DOI indexes defined in the user’s profile for the nodes initially activated, and a value 0 for the remaining nodes. Next, the activation levels of the user’s preferences are propagated through the SA network by using the Hopfield Net algorithm, which is in charge of selecting the items with high levels to be recommended to the user. The principle of parallel search of this algorithm is especially beneficial for our personalization approach, because the capability of activating in parallel all the nodes in the user’s SA network permits to carry out the spreading process in an efficient way. Specifically, the algorithm computes the activation level of each node in the user’s SA network by adding the contribution from all of its neighbor nodes. This contribution considers both the activation level of each neighbor node and the weight of the link (real or virtual) joining it to the considered node. For that reason, the more relevant the neighbors of a node (i.e. the higher activation levels) and the stronger the relationships among them and the considered node (i.e. the greater weights of links), the more significant this node will be for the user. This contribution is incorporated as an argument into the sigmoid function used by Hopfield Net (see Eq. (1)). As shown in Eq. (3), the weight of a link is computed starting from either the DOI indexes of the two joined nodes (if they are defined in the user’s profile) or from their semantic intensity values (otherwise). Consequently, it holds that: – The sigmoid function measures the highest activation values for nodes which are connected both to class instances very appealing to the user (whose DOI indexes are very significant), and to nodes greatly related to his/her positive preferences (whose semantic intensity is very high). – Analogously, according to the internals of our content-based strategy, the sigmoid function quantifies low activation levels for class instances which are related to the users’ negative preferences, thus preventing from suggesting these items. Finally, our strategy selects the items to be suggested to the user. Specifically, the strategy recommends only the items of the user’s SA network whose activation level is greater than a configurable threshold d. This parameter is clearly dependent on the application domain and the recommender system that adopts our strategy. Anyway, the values must be always very high (close to 1) to guarantee that the items suggested are closely related to the user’s preferences.3 5. A sample scenario The research work of our content-based recommendation strategy has been tested in the scope of a TV recommender system (named R-AVATAR), which is being deployed over the cable networks of a Spanish operator with about 80,000 subscribers that broadcasts daily 43 TV channels. The goal of this system is to identify potentially appealing programs to each subscriber among the contents available in the digital stream. In this section, we illustrate how to select the TV programs that are most appealing to a user by considering the knowledge formalized in the excerpt from the TV ontology depicted in Fig. 2. Even though this ontology contains a reduced number of classes, properties and instances, it serves to highlight the differences between our reasoning-based recommendations and those offered by traditional (syntactic) content-based approaches. Assume a TV viewer U whose positive and negative preferences are shown in Table 1, including the TV programs U liked and disliked in the past, his/her DOI indexes (in brackets), and the classes under which these programs are categorized in the hierarchy of genres defined in the TV ontology. 3 As a guidance, note that we have used the parameters h1 = 10, h2 = 0.8 and n = 0.08 (for the Hopfield Net algorithm), and recommendation thresholds d in the range [0.78, 0.9] in the tests carried out in the Digital TV field. 10 Y. Blanco-Fernández et al. / Information Sciences xxx (2011) xxx–xxx Please cite this article in press as: Y. Blanco-Fernández et al., Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems, Inform. Sci. (2011), doi:10.1016/j.ins.2011.06.016