Automated Ontology Evolution as a Basis for Adaptive Interactive Systems Elmar P. Wach STI Innsbruck, University of Innsbruck/ Elmar/P/Wach eCommerce Consulting Technikerstraße 21a, 6020 Innsbruck, Austria/ Hummelsbüttler Hauptstraße 43, 22339 Hamburg, Germany +49 172 713 6928 elmar.wach@sti2.at/ wach@elmarpwach.com ABSTRACT The research presented in this paper aims at realising an 1. INTRODUCTION Today, the user in the Internet gets overflowed with information automated ontology evolution process based on feedback without and products that she should purchase. Not only becomes it a human inspection. For that, a generic adaptation strategy difficult for her to take the right buying decision, but also don’t consisting of a feedback transformation strategy and an ontology match many search results her needs. Hence, recommender evolution strategy is formulated. It decides when and how to systems in e-commerce applications have become business evolve by evaluating the impact of the evolution in the precedent relevant in filtering the vast information available in the Internet feedback cycle. These strategies are implemented in a feedback (and e-shops) to present useful search results and product transformer component and an adaptation manager component recommendations to the user. respectively, constituting a new adaptation layer. The adaptive ontology is evaluated with an experiment and validated with a As the range of products and customer needs and preferences real-world conversational content-based e-commerce change – and they will change even more frequently – it is recommender system as use case. necessary to adapt the recommendation process. Doing that manually is inefficient and usually very expensive. Categories and Subject Descriptors Therefore, this research proposes an automated adaptation of the G.2.2 [Discrete Mathematics]: Graph Theory – graph recommendation process by utilising semantic technology and algorithms, graph labeling. H.3.3 [Information Storage and processing user feedback. Retrieval]: Information Search and Retrieval – relevance feedback. H.3.5 [Information Storage and Retrieval]: Online The shortcomings of a manual adaptation of the recommendation Information Services – commercial services, web-based services. process based on user feedback are aimed to be solved with a I.2.4 [Artificial Intelligence]: Knowledge Representation system based on product domain ontologies (PDO) modelling the Formalisms and Methods – representations (procedural and rule- products offered in the e-commerce application and automatically based), semantic networks. I.2.6 [Artificial Intelligence]: evolving with processing user feedback. As the PDO describes the Learning – concept learning, knowledge acquisition. K.4.3 products formally, it offers a higher computability than [Computers and Society]: Organizational Impacts – automation conventional product descriptions and, hence, facilitates automated processing of information. General Terms In order to get the system user-driven, user feedback is gathered Algorithms, Management, Measurement, Design, by unobtrusively monitoring user needs. The more information is Experimentation, Standardization, Languages. available from a user, the better the adaptation to her needs can be. Hence, implicit and explicit feedbacks provided via feedback channels are evaluated. Implicit feedback is given by the user as a Keywords side-effect of her usage behaviour, e.g. by clicking on the product Ontology Evolution, Ontology Versioning, Recommender recommended. Explicit feedback could be provided by answering Systems, Self-Adapting Information Systems, Algorithms. questions about her satisfaction with the application. As this effort cannot be expected from a user, an alternative is to extract feedback from the Web that could also deliver new information and aspects about the products offered. In order to focus this research on developing an automated ontology evolution, the feedback is assumed to be given. On a more abstract level, this research aims at realising an automated ontology evolution process based on feedback without a human inspection. Copyright is held by the author. Topics of the SEMAIS 2011 workshop related to this research: SEMAIS’11, February 13, 2011, Palo Alto, CA, USA • What are the major technical challenges for developing or considering also how identified conflicts can be solved, e.g. when generating user interfaces based on semantic models? moving a sub-concept. This paper aims to answer the above question with a generic By following the principles of adaptive systems [3], the approach. adaptation strategy is implemented in a new adaptation layer • For which kind of systems or applications are semantic models consisting of components in which the user feedback gets particularly useful? transformed (i.e. Feedback Transformer) and the respective The use case in this paper is a recommender; for which other actions are decided and initiated (i.e. Adaptation Manager). systems or applications can it be useful? • Additional question: Which ontological information and its changes (properties, etc.) are requested by adaptive interactive 3.1 Feedback Transformation Strategy systems? In order to automatically process feedback, i.e. transforming it into ontology input, an adequate feedback transformation strategy has to be formulated and implemented. It has to allow for different 2. RELATED WORK feedback channels as well as different kinds of feedback. This Previous approaches to the topic of this research can be found in strategy is implemented in the feedback transformer component concepts for ontology evolution like formulated frameworks for depicted in figure 1. In the Feedback Transformer the ontology ontology evolution, e.g. [6], [7], [8], [14], [16], [18]. Due to the affected by the feedback reported is identified, the feedback is specific challenges of the present research like the automated analysed and transformed, and eventually get related to the ontology evolution process, none of the identified frameworks can precedent feedback. be completely used as basis, e.g. all of the frameworks include a step for the human inspection of the ontology changes before they are executed. The closest work to the research in this paper is [16] – in the six phase evolution process, two steps include manual activities, namely (i) “Implementation” in which the implications of an ontology change are presented to the user and have to be approved by her before execution, and (ii) “Validation” in which performed changes can get manually validated. The research in this paper proposes an extension of [16] towards an automated ontology evolution by developing a generic adaptation strategy and further introducing a complete feedback cycle based on the ontology usage that eliminates the implementation and validation Figure 1. Conceptual architecture of the feedback transformer steps of above – an ontology change needs those manual steps no component longer, as an insufficient change would be alerted by a negative feedback and get corrected automatically. Basically, the strategy comprises the following steps: The approaches to the identified recommender systems [1], [2], 1. Gather feedback from the different channels [4], [11], [12], [13] research the impact on the recommendation 2. Transform different feedback types result by using the different recommender types (i.e. content- 1. Report transformed feedback to the next component based filtering, collaborative filtering, hybrid approaches) and mostly utilising domain and user ontologies, whereas the feedback Ad 1. Each feedback channel provides user feedback as RDF gets processed in the latter one. None of them combines an e- triples at separate SPARQL endpoints. The RDF triples are commerce domain ontology with the processing of implicit and retrieved by the Feedback Transformer and captured in a semantic explicit user feedbacks. feedback log as instances of the feedback ontology (confer next paragraph). 3. ADAPTATION STRATEGY Ad 2. The feedback ontology is a prerequisite for the meaningful For realising an automated ontology evolution, a generic analysis of the feedback [17]. In the present research, it models adaptation strategy consisting of a feedback transformation the feedback at the product level and additionally contains all strategy and an ontology evolution strategy is formulated. It product names of the product ontologies. The structure of the decides when and how to evolve by evaluating the impact of the feedback ontology enables reasoning about a product and its evolution in the precedent feedback cycle. The first question ratings including the historical development as well as identifying defines the (temporal and causal) trigger initiating the ontology properties and relations to be newly added to the product change. Basically, this is receiving and transforming the feedback ontology. Accordingly, we distinguish between the three feedback into ontology input and will be addressed with a feedback types “KPI1 trend”, “product rating”, and “new property”. The transformation strategy (confer chapter 3.1). root concept is “Feedback”. Its hierarchy consists of the sub- concepts “KPI trend”, “product rating”, and “new property”. The second question defines the changing of the ontology Appropriate relations like “previousRating” model the history of including instance data. This is denoted by ontology evolution the ratings. referring to the activity of facilitating the modification of an ontology by preserving its consistency [19]. This will be addressed with an ontology evolution strategy (confer chapter 3.2) 1 Key Performance Indicator, measured in the application layer The first two feedback types are converted by either a simple transformation or a feedback evaluation algorithm to values in the range [+1…-1] relating the current transformed feedback to the one in the precedent cycle. For the feedback type “product rating” the RDF feedback includes the product name and rating but no new potential property. The feedback is transformed with a feedback evaluation algorithm. In the first step, the impact of the ontology evolution on the KPI (e.g. conversion rate and click-out rate) is calculated for each product and feedback channel. In the next step, all feedback channels are aggregated at the product level. Finally, a trend Figure 2. Conceptual architecture of the adaptation manager metric is calculated relating the current transformed feedback to component the one in the precedent cycle. Basically, the strategy comprises the following steps: For the feedback type “new property” the RDF feedback includes the product name and a new potential property to be eventually 4. Gather feedback trends added to the product ontology, e.g. information like aspects or 5. Associate ontology changes with evolution strategies relevant features of a product. This feedback type is not covered 6. Ensure a consistent ontology evolution by the feedback evaluation algorithm. A new sub-property for the aspect/ feature is created in the feedback ontology and its count Ad 4. In each feedback cycle the transformed feedback gets gets related to the count of all properties in the respective PDO. reported to the Adaptation Manager. The feedback is based on the When reaching a defined threshold, the new property is added to product level. Each reported feedback is captured in a trend log at the respective PDO. the product level. The semantic feedback log captures the exact sequence of the Ad 5. The central task of the ontology evolution strategy and the reported feedbacks. Each feedback is associated with the Adaptation Manager is to choose the right evolution, i.e. ontology respective product (i.e. the RDF feedback contains the changes, for the transformed feedback. corresponding product name) and represented as instances of the [9] introduced a meta-ontology for the ontology evolution sub-concepts of “Feedback”. These instances contain the product enabling representation, analysis, realisation, and sharing of name, feedback channel, date and time of the feedback, rating, ontological changes. Each possible change is represented as a and the certainty of the rating as well as the number of properties concept in that evolution ontology having an evolution log as contained in the product ontology. The log allows the analysis of instance capturing the changes. A central element in the the feedback development. framework of [7] are a change log and an ontology of change Ad 3. After having transformed the different feedback types, the operations for OWL describing basic ontology change operations2 calculated metrics relating the current feedback to the feedback in and complex change operations composed of multiple basic the precedent cycle are reported to the next component, i.e. the operations. This research aims at utilising the ontology of change Adaptation Manager. operations sketched above. Derived from user scenarios, evolution strategies are defined 3.2 Ontology Evolution Strategy reflecting different behaviours and associating ontology changes, The ontology evolution strategy defines how the PDO change. It namely: associates the transformed feedback values to evolution actions and ensures a consistent new version of a PDO. This strategy is • Risky Evolution (“always evolve differently”): Regardless of implemented in the adaptation manager component depicted in the feedback trend between two consecutive feedback cycles, figure 2. In the Adaptation Manager the structure of the respective other complex ontology change operations are executed ontology get dynamically analysed with SPARQL SELECT • Progressive Evolution (“learn from the past”): Depending on statements and the ontology changes (e.g. switching individuals, the leap of the trend, same or different complex ontology switching annotation property labels and comments, changing change operations are executed; in case of a negative trend, it annotation property priorities, adding new properties) are is optional to either do a different complex ontology change executed with SPARQL CONSTRUCT rules according to operation or a rollback; additionally, with a threshold predefined evolution strategies. indicating the increase of the trend between the current and the precedent cycle the “risk” of the evolution can be adjusted and the strategy tuned towards the Risky Evolution (with a higher threshold) • Safe Evolution (“only revert negative trends”): In case of a negative trend, a rollback is executed 2 Basic ontology change operations modify only one specific feature of an OWL ontology • Rollback (“undo the ontology changes”): Reverts the The whole adaptation strategy and its implementation via the ontology changes from the precedent feedback cycle and is components Feedback Transformer and Adaptation Manager based on any reason or decision of the manager; it is allow eliminating both manual steps in the six phase evolution executed only once but can be manually chosen multiple process of [16]: times • Phase “Implementation” (ontology changes are manually Ad 6. After having chosen the ontology change operations to be approved before execution): Nobody has to do that, as the executed, the ontology has to evolve depending on rules and by ontology evolution is seen as a complete feedback cycle – an retaining its consistency to finally provide its knowledge to the insufficient ontology change is indicated by decreased KPI application layer. and gets revised according to the evolution strategy chosen The existing research about ontology evolution is based on the • Phase “Validation” (performed changes can get manually work about data schema evolution but focuses on the specific validated): As the ontology changes are predefined, only needs of ontologies, e.g. [10], [15], [16]. valid changes are executed, and nobody has to validate them To execute ontology changes, an ontology evolution algorithm has to be formulated. The following prerequisites have to be 4. EVALUATION AND VALIDATION respected: The automatically evolved ontology is going to be compared with a manually evolved one by setting up and evaluating an • The basic and complex ontology change operations have to experiment with ontology experts. Those analyse the feedbacks be defined formally delivered and decide the ontology changes to be executed. • It has to be defined when an ontology is inconsistent, i.e. an Eventually, the ontology resulted from this manual evolution is ontology consistency model has to be formulated; the compared with the automatically evolved one regarding the preconditions and postconditions of the change operations evaluation criteria consistency, completeness, conciseness, have to be checked before execution expandability, and sensitiveness [5]. • The options for a consistent ontology evolution have to be The validation of this research is done with a use case by utilising identified and the “best” evolution path chosen; in the a real-world conversational content-based e-commerce present research the belief revision principle of minimal recommender system and two feedback channels – the Web change will be followed [8]; eventually, the ontology application and information extracted from Linked Open Data. As evolution algorithm can be formulated the recommender is already used in live e-commerce applications, the evaluation of the system adaptations is a real-world scenario. When evolving the ontology, it has to be clear how the ontology has been evolved over time, i.e. the different ontology evolutions The recommender is based on PDO that semantically describe the have to be versioned. In the context of this research this is of products offered in e-commerce applications according to the paramount importance, for (i) the ontology changes in the current GoodRelations ontology.3 feedback cycle are derived from the changes in the precedent The success of such a system is usually defined by analysing KPI cycle and (ii) an undoing of the changes in the precedent feedback like the achieved conversion rate (i.e. customers-to-recommender cycle, i.e. a rollback, has to be realisable. users ratio) or click-out rate (i.e. clicks-to-recommendations The preferred concept of ontology versioning is change-based ratio). versioning (i.e. each state gets its own version number and The evaluation scenario is to test and evaluate the impact of the additionally stores information about the changes made), because ontology evolution by utilising the formulated evolution it facilitates change detection, integration, conflict management strategies, i.e. Risky Evolution, Progressive Evolution, and Safe [9], and it allows the interpretation how ontology changes Evolution. influence the KPI. A change-based versioning can be best realised by tracking the ontology changes in a semantic log [9]. The impact of the ontology evolution will be analysed and evaluated with regard to the respective KPI at the application The change ontology models the applicable changes and meta- level after each to be defined number of accomplished information and provides the semantics of all possible ontology recommendation processes and reported to the ontology. changes. The root concept is “Change”. Its hierarchy consists of the sub-concepts “complex ontology change operations” and According to the respective results and feedbacks reported, the “basic ontology change operations”. Appropriate relations like ontology evolves. The ontological knowledge is provided to the “previousChange” model the history of the ontology changes and application layer, and eventually adapted recommendations are construct the sequence of the required changes. The structure of presented to the customer. The feedback circle of the automated the change ontology enables reasoning about changes including system concludes with re-evaluating the KPI after having again their historical development. reached the defined number of recommendation processes. The semantic change log captures the exact sequence of the The intended results are a highly adaptive system and eventually ontology changes executed. Each change is represented as better recommendations given to the user leading to an increase of instances of the sub-concepts of “Change”. The log allows the the defined KPI. The expected business impacts are a higher analysis of the change development including realising a rollback. 3 www.purl.org/goodrelations customer satisfaction and loyalty and eventually increased [3] Broy, M. et al. 2009. Formalizing the notion of adaptive revenue for the provider of the application. system behavior, Proceedings of the 2009 ACM Symposium on Applied Computing (SAC ’09), pp. 1029-1033. This evaluation procedure will be executed for all three evolution strategies and evaluated analogously. [4] Drachsler, H. et al. 2008. Effects of the ISIS recommender system for navigation support in self-organised learning An interesting result of the evaluation scenario would be that one networks, Proceedings of Special Track on Technology of the three evolution strategies leads to a higher increase of the Support for Self-Organised Learners, pp. 106-124. KPI. [5] Gómez-Pérez, A. 2001. Evaluation of ontologies, In case a predominant evolution strategy is identified, it can be International Journal of Intelligent Systems, Volume 16, pp. interpreted that the historic development of changing the ontology 391-409. (i.e. doing the same change again versus doing a different change) [6] Haase, P. et al. 2005. A framework for handling has a significant influence on the customer satisfaction. Though, inconsistency in changing ontologies, Proceedings of the this can in the case of same changes only be valid within a 2005 International Semantic Web Conference (ISWC05), pp. realisable frame, e.g. it is not possible to move up a sub-concept 353-367. in the concept hierarchy infinitely times. [7] Klein, M. and Noy N. F. 2003. A component-based framework for ontology evolution, Proceedings of the IJCAI- 5. CONCLUSION 03 Workshop on Ontologies and Distributed Systems. The need for automatically updating and evolving ontologies is urging in today’s usage scenarios. The present research tackles an [8] Konstantinidis, G. et al. 2007. Ontology evolution: A automated process for the first time (to the best knowledge of the framework and its application to RDF, Proceedings of the author). The reason for that can be found in the ontology Joint ODBIS & SWDB Workshop on Semantic Web, definition “formal, explicit specification of a shared Ontologies, Databases. conceptualisation”. “Shared” means the knowledge contained in [9] Mädche, A. et al. 2002. Managing multiple ontologies and an ontology is consensual, i.e. it has been accepted by a group of ontology evolution in Ontologging, Proceedings of the IFIP people. Entailed from that, one can argue that by processing 17th World Computer Congress – TC12 Stream on Intelligent feedback in an ontology and evolving it, it is no longer a shared Information Processing, pp. 51-63. conceptualisation but an application-specific data model. On the [10] Mädche, A. et al. 2003. Managing multiple and distributed other hand, it is still shared by the group of people who are using Ontologies on the Semantic Web, The VLDB Journal – The the application. It may even be argued that the ontology has been International Journal on Very Large Data Bases, Volume optimised for the usage of that group (in a specific context or 12, Issue 4, pp. 286-302. application) and, hence, is a new way of interpreting ontologies: They can also be a specifically tailored and usage-based [11] Maidel, V., Shoval, P., Shapira, B., Taieb-Maimon, M. 2008. knowledge representation derived from an initial ontology – an Evaluation of an ontology-content based filtering method for ontology view, preserving most of the advantages like the support a personalized newspaper, Proceedings of the 2008 ACM of automatically processing information. Thus, this changed way conference on Recommender systems, pp. 91-98. of conceiving ontologies could facilitate the adoption and spread [12] Middleton, S. E., De Roure, D. C., Shadbolt, N. R. 2001. of using this powerful representation mechanism in the real world, Capturing knowledge of user preferences: Ontologies in as it is easier to accomplish consensus within a smaller group of recommender systems, Proceedings 1st international people than a larger one. conference on Knowledge capture, pp. 100-107. [13] Middleton, S. E., Shadbolt, N. R., De Roure D. C. 2003. 6. ACKNOWLEDGMENTS Capturing interest through inference and visualization: The research presented in this paper is funded by the Austrian Ontological user profiling in recommender systems, Research Promotion Agency (FFG) and the Federal Ministry of Proceedings 2nd international conference on Knowledge Transport, Innovation, and Technology (BMVIT) under the FIT- capture, pp. 62-69. IT “Semantic Systems” program (contract number 825061). [14] Noy, N. F. et al. 2006. A framework for ontology evolution in collaborative environments, Proceedings of the 2005 7. REFERENCES International Semantic Web Conference (ISWC05), pp. 544- [1] Aktas, M. S., Pierce M., Fox, G. C., Leake D. 2004. A Web 558. based conversational case-based recommender system for [15] Plessers, P. 2006. An approach to Web-based ontology ontology aided metadata discovery, Proceedings 5th IEEE/ evolution, Ph.D. Thesis, Department of Computer Science, ACM International Workshop on Grid Computing, pp. 69- Vrije Universiteit Brussel. 75. [16] Stojanovic, L. et al. 2002. User-driven ontology evolution [2] Blanco, Y. et al. 2005. AVATAR: An approach based on management, Proceedings of the 13th International semantic reasoning to recommend personalized TV Conference on Knowledge Engineering and Knowledge programs, Proceedings 14th International conference on Management (EKAW ’02), pp. 285-300. World Wide Web, pp. 1078-1079. [17] Stojanovic, N. and Stojanovic, L. 2002. Usage-oriented evolution of ontology-based knowledge management systems, LNCS 2519, pp. 1186-1204. [18] Stojanovic, N. et al. 2003. The OntoManager – a system for [19] Suárez-Figueroa, M. C. and Gómez-Pérez, A. 2008. Towards the usage-based ontology management, LNCS 2888, pp. a glossary of activities in the ontology engineering field, 858-875. Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC ’08).