=Paper=
{{Paper
|id=None
|storemode=property
|title=Automated Ontology Evolution as a Basis for Adaptive Interactive Systems
|pdfUrl=https://ceur-ws.org/Vol-747/paper12.pdf
|volume=Vol-747
}}
==Automated Ontology Evolution as a Basis for Adaptive Interactive Systems==
https://ceur-ws.org/Vol-747/paper12.pdf
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).