This research proposes an automated OWL product domain ontology (PDO) evolution (without a human inspection) based on given user feedback and enhancing an existing ontology evolution concept. Its manual activities are eliminated by formulating an adaptation strategy for the conceptual aspects of an automated PDO evolution and establishing a feedback cycle. The adaptation strategy consists of a feedback transformation strategy and a PDO evolution strategy and decides when and how to evolve by evaluating the impact of the evolution on the application. An evolution heuristic and evolution strategies are utilised. The adaptation strategy was validated/ firstly “instantiated” by applying it to a real-world conversational content-based ecommerce recommender system as use case. The evolved PDO is going to be evaluated with an experiment and validated with the use case as well.
1. INTRODUCTION
Recommender systems in e-commerce applications have become business relevant in filtering the vast information available in eshops (and the Internet) to present useful recommendations to the user. As the range of products and customer needs and preferences change, it is necessary to adapt the recommendation process. Doing that manually is inefficient and usually very expensive.
Recommenders based on product domain ontologies1 (PDO) can extract questions about the product characteristics and features to investigate the user preference and eventually recommend products that match the needs of the user. By changing the PDO, such a recommender generates different questions and/ or their order and herewith adapts the recommender interface to the user preference. Hence, an automated adaptation of the recommendation process can be realised by automatically evolving the PDO2. The high cost of the manual adaptation of the recommendation process and the underlying PDO can herewith be minimised.
This research proposes an automated OWL PDO evolution (without a human inspection) based on given user feedback3 and enhancing an existing ontology evolution concept. Its manual activities are eliminated by formulating an adaptation strategy for the conceptual aspects of an automated PDO evolution and establishing a feedback cycle. Automatically evolving the PDO is more efficient and less expensive than manually doing it. The present research tackles an automated process for the first time (to the best knowledge of the author).
Figure 1 depicts the starting basis schematically.
In the data modelling layer the OWL PDO evolution is induced by
different kinds of user feedback, i.e. from external and internal
data sources. When evolving the PDO, it can be necessary to
adapt instance data (i.e. products) as well in order to keep them
correctly annotated. Afterwards, the new PDO version including
associated instance data is provided to the application layer. There
1 A product domain ontology (PDO) is defined as the formal,
explicit specification of a shared conceptualisation of a product
description based on OWL DL; this definition is derived from
[
Application Layer (e.g. Recommender System) (Assumption: Given)
OWL/ RDF data
domain ontology evolution be realised based on feedback?
Previous approaches in the topic of this research can be found in
concepts for ontology evolution like formulated frameworks for
ontology evolution.
[
Ontologging6 system. Evolution strategies have been formulated
defining elementary and composite changes for executing a
change request and eventually deciding the evolution path. [
Commission project Ontologging
changing ontologies and have defined a framework consisting of
four approaches addressing the consistent ontology evolution, the
repairing of inconsistencies, the reasoning with inconsistent
ontologies, and multi-version reasoning. For the first three
approaches consistency algorithms have been formulated. A
consistent ontology evolution is ensured by removing axioms that
are structurally connected with the conflicting axioms. [
Due to the specific challenges of the present research like the
automated ontology evolution process, none of the frameworks
discussed can be completely used as basis, e.g. all 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 [
and gets revised according to the evolution strategy chosen.
The aim of this research is to combine the use of PDO with processing user feedback. The work focuses on how the given
feedback can lead to a self-improvement of the semantic application by adapting the PDO. In this context selfimprovement means that by automatically processing user feedback and evolving the PDO, the defined key performance indicators (KPI) of the application will increase.
The use case is a real-world conversational content-based ecommerce recommender system based on PDO that semantically describe the products offered in e-commerce applications according to GoodRelations9. Four types of PDO changes are defined with the following impact on the user dialogue in the recommender system: • • • •
Switching individuals (i.e. properties are related to other
individuals within the same class): This leads to a different
clustering of the questions
Switching datatype property ranges (i.e. properties get
Boolean ranges instead of string ranges and vice versa
(where applicable)): This leads to textual modifications of
the questions
Switching annotation properties label and comment (i.e.
properties get different labels and comments extracted from
another information source): This leads to textual
modifications of the questions (and maybe a need-based sales
approach instead of a technology-prone one)
Changing annotation property priority (i.e. different priority
values): This leads to a different ranking of the questions and
skips the ones with low priorities
In this paper the PDO change switching individuals is used as an
example (confer section 4.2). A digital camera has a feature
HDMI. This PDO change defines in which feature-related section
the question is nestled whether the camera should offer HDMI.
The success and thus the KPI of an e-commerce recommender are
usually defined by the click-out rate (i.e.
clicks-torecommendations) or conversion rate (i.e.
customers-torecommender users). The user gives feedback to the quality of a
product recommendation in following the recommendation (i.e.
click-out) or even buying the product (i.e. conversion).
In the approach a six step adaptation strategy for the conceptual
aspects of an automated PDO evolution has been formulated and a
feedback cycle established. The adaptation strategy answers the
questions when and how to evolve the PDO by evaluating the
impact of the evolution in the precedent feedback cycle. The first
question defines the (temporal and causal) trigger initiating the
PDO change. Basically, this is receiving and transforming the
feedback into ontology input and will be addressed with the
feedback transformation strategy. The second question defines the
changing of the PDO with annotated instances. This is evolving
the PDO and will be addressed with the PDO evolution strategy.
Due to space limitations and the focus on realising a user-centric
evaluation, the adaptation strategy is not elaborated in this paper.
The strategy is used to concisely describe the application for
which the automated PDO evolution should be implemented and
the impacts of PDO changes on the application behaviour. The
interested reader is referred to [17].
9 www.purl.org/goodrelations
3.1 Evolution Heuristic and Evolution
Strategies
The automated ontology evolution is realised by utilising an
evolution heuristic and evolution strategies. Those are defined in
the fifth step of the adaptation strategy “Decide the adequate PDO
evolution”. The impact of the PDO change is measured in the
Feedback Transformer (confer section 3.2) component by
calculating the Success Trend ST for the new user feedback from
the application layer and external data sources. The ST is analysed
by a heuristic that defines the PDO change to be executed. A
heuristic is a strategy that uses accessible and loosely applicable
information to solve a problem of a human being or a machine
[
The PDO evolution is decided based on the ST. In case the feedback includes information extracted from the PDO (e.g. property-based feedback), the subsequent evolution (i.e. type of PDO change) is defined by implementing the ST in the same representation as before (e.g. ontological entity, range), and neither statistical means nor a heuristic has to be applied. This research proposes to additionally formulate evolution strategies that decide the general evolution behaviour (e.g. executing the same type of PDO change or a rollback) by correlating the types of PDO changes needed to the ST calculated. Additionally, the path for determining the initial ST has to be defined, e.g. the order of the different types of PDO changes and for which PDO they are executed (i.e. ramp-up of the evolution strategies). The philosophy should be that the development (and its strength) of the precedent ST defines the next type of PDO change to distinguish different evolution impacts.
A positive ST means a positive trend (i.e. an increase) of the metrics, a negative the opposite. The larger the figure is, the stronger the development of the metrics (in either direction) from the precedent to the current cycle has been. So, there are two criteria (i.e. ST and its strength) to decide about the next type of PDO change. Basically, there can be two resulting user behaviours in the e-commerce recommender system:
The user is satisfied with the product recommendation and clicks to see the detail page or order it; in that case the metrics increase, but it still has to be decided if a change should be made The user is not satisfied with the product recommendation and leaves the recommender; the metrics decrease, though we do not know why she was not pleased, and a PDO change is advisable • In the first case, one can argue either way – a change is luring to even further increase the metrics. On the other hand, one could keep everything as it is and wait for the next feedback. The latter case is more urging for a change. It has still to be decided if it is a change or just a rollback to retrieve the previous setting. So, it is advisable to define evolution strategies reflecting different behaviours with associated types of PDO changes. In the following, these strategies are predefined and discussed. Risky Evolution: An evolution is induced in either case, i.e. a positive or a negative trend. Different types of PDO changes than in the precedent feedback cycle are executed. This behaviour tries to radically improve the metrics by all means and can be described as “always evolve differently”. The decision criteria are as follows: • •
Increase of the KPI (i.e. 0 ≤ ST ≤ 1)
Decrease of the KPI (i.e. -1 ≤ ST < 0) Progressive Evolution: • • • • • An evolution depends on the leap in the ST between two consecutive feedback cycles and can be fine-tuned with a threshold defining the trend significance (i.e. the increase of the ST between the precedent and the current cycle). In case of a significant positive trend, the same type of PDO change as in the precedent feedback cycle is executed. In case of a moderately positive trend, a different type of PDO change than in the precedent feedback cycle is executed. In case of a negative trend, it is optional to either do a different type of PDO change than in the precedent feedback cycle or a rollback (to be selected in the administration interface of the Adaptation Manager). This behaviour tries to repeat a significant increase by the same means but gives also the option to revert a negative development. It can be described as “learn from the past”. Additionally, the “risk” of the evolution can be adjusted with the threshold. The higher it is the more unlikely the same type of PDO change as in the precedent feedback cycle is executed, and the strategy is tuned towards the Risky Evolution (with a higher threshold). Initially, the threshold is defined to be 20%10 and can be changed in the administration interface as well. The decision criteria are as follows:
Significant increase of the KPI (for the beginning, the threshold is defined to be 20%, i.e. 0,2 ≤ ST ≤ 1) Moderate increase of the KPI (i.e. 0 ≤ ST < 0,2)
Decrease of the KPI (i.e. -1 ≤ ST < 0) Safe Evolution: An evolution is induced only by a negative trend. In that case, a rollback is executed. This behaviour tries only to revert a negative development. It can be described as “only revert negative trends”. The decision criteria are as follows:
Increase of the KPI (i.e. 0 ≤ ST ≤ 1)
Decrease of the KPI (i.e. -1 ≤ ST < 0)
10 Increase of the ST by 20 basis points between the precedent and
the current feedback cycle
Rollback:
This “strategy” reverts the PDO changes from the precedent
feedback cycle (i.e. rolling back to the precedent PDO version)
and is based on any reason or decision of the manager. It is
executed only once but can be manually chosen multiple times.
The behaviour can be described as “undo the PDO changes”.
The evolution strategies introduced above are considered as basic
categories. They can be fine-tuned with regard to the associated
types of PDO changes as well as the threshold defining the trend
significance. Table 1 sums up the predefined evolution strategies,
decision criteria (ST), and the type of PDO changes to be
executed in the feedback cycle.
3.2 Implementing the Strategy by
Programming an Application
By following the principles of adaptive systems [
Application Layer
Data Modelling Layer Adaptation Feedback Manager Transformer
New Adaptation Layer
III.
Evaluation
The whole evolution cycle is based on the generic change process
model [
Phase “initiation” – Activities: Requesting the change and analysing/ planning the change Phase “execution” – Activity: Implementing the change Phase “evaluation” – Activity: Verifying/ validating the change The three layers (i.e. application layer, data modelling layer, and adaptation layer) interact during the three phases of the generic change process model forming the basis of the automated PDO evolution process.
In the first phase “initiation” the different kinds of user feedback are delivered to the adaptation layer and thus a PDO change requested. As the PDO is the backbone of a semantic application, the feedback is assumed to be RDF data. This feedback is converted to ontology input by the Feedback Transformer according to the feedback transformation strategy. The Feedback Transformer accesses the user feedback channels programmatically via SPARQL endpoints and identifies the PDO affected with SPARQL SELECT statements. Eventually, the Feedback Transformer calculates the Success Trends ST for each feedback channel, e.g. by a simple value transformation or by calculating the relative frequencies of the property values in the feedback. Then, the PDO evolution is prepared by identifying the next PDO change with the transformed feedback by the Adaptation Manager. The system has to decide which evolution actions to take according to the PDO evolution heuristic and strategy. The Adaptation Manager analyses the transformed feedback with a tabu search metaheuristic that chooses the PDO change with the highest ST. The tabu criteria are implemented for each type of feedback. Additionally, the predefined evolution strategies (i.e. Risky Evolution, Progressive Evolution, Safe Evolution, Rollback) are implemented and ramped-up. For determining the initial ST, the different types of PDO changes are sequentially executed in an alphabetical order with an exemplary PDO. These values are then valid as starting basis for all PDO. After this phase, the evolution strategy decides whether the (i) same or (ii) another type of PDO change is executed. In (i), a PDO change within the same type of PDO change is executed and ST(t+1) calculated, except a tabu criterion defined by the evolution heuristic is met. In this case, another type of PDO change is executed in contrary to the evolution strategy. In (ii), the type of PDO change and the PDO change to be executed are determined by the evolution heuristic, and ST(t+1) is calculated. In the second phase “execution” the changes get implemented in the data modelling layer directed by the PDO evolution heuristic and strategy and by retaining a consistent PDO including correctly annotated instance data. In the Adaptation Manager the predefined PDO changes (for the use case they are switching individuals, switching datatype property ranges, switching annotation properties label and comment, changing annotation property priority, confer section 3.) are implemented and thus ensure a consistent ontology evolution. They are executed with SPARQL CONSTRUCT rules or programmatically. Eventually, the versioning is implemented according to the change-based concept and utilising an ontology with annotated logs. The new PDO version with associated instances is provided to the application layer.
The third phase “evaluation” concludes the feedback cycle by measuring the impact of the change. This is done by calculating adequate metrics relating the currently evaluated feedback from the application layer and external data sources reported to the adaptation layer to the precedent feedback.
The process from the feedback type to the resulting type of PDO change is depicted in the activity diagram in figure 3. 4. EVALUATION AND VALIDATION The adaptation strategy has been validated/ “instantiated” by applying it to the use case. As this recommender is already used in live applications, it is a real-world scenario. In a conversational approach the actions and modifications done in the adaptation layer mainly lead to a changed user dialogue.
Implicit user feedback is derived from user interactions in the application layer and gathered by unobtrusively monitoring user needs. Explicit user feedback is gathered by extracting information from various websites. Both feedback channels deliver RDF data via separate SPARQL endpoints programmatically accessible.
Applying the adaptation strategy could be done quite smoothly. Only minor aspects of the strategy were clarified, restructured, and reformulated. After having applied the strategy, the use case was concisely described and conceived by the ontology engineer. Moreover, the result formed the basis of the technical specification and thus the development of the adaptation layer. Due to space limitations the “instantiation” of the adaptation strategy is not completely elaborated in this paper. In the following the evolution heuristic based on tabu search is introduced (excluding its ramp-up). 4.1 Characteristics of the Evolution Heuristic The evolution heuristic determines the PDO change to be executed. As the evolution strategies define if the same type of PDO change is repeated or another one is executed, the type has still to be determined in the latter case as well as the PDO change (e.g. switching the property weight from the individual WeightAndDimension to the individual GeneralCharacteristics). For this, a tabu search metaheuristic is utilised with the following characteristics: (i) Always the impact of the evolution in the precedent feedback cycle is evaluated, (ii) only one implicit PDO change is executed per cycle, and (iii) “greedy” approach: The evolution heuristic chooses the PDO change with the highest ST. There are two types of ST for determining the PDO change to be executed: (i) STf_pdo_change_x is the ST for the forward PDO change x, and (ii) STb_pdo_change_x is the ST for the backward PDO change x (i.e. reverts the forward change). Forward PDO changes to be executed are determined with the highest STf_pdo_change_x, backward PDO changes with the highest STb_pdo_change_x.
In the following the tabu criteria are defined. 4.1.1 Specific Tabu Criteria sw and ch The specific tabu criteria are specifically calculated for each type of PDO change. 4.1.1.1 Allowed Number of Horizontal Switches sw With sw one (set of) ontological entity of a PDO within the same type of PDO change is switched, e.g. a PDO change of one (set of) property or (set of) individual – most of times there is only one switch possible like changing the individual, the property range, or the annotation properties label and comment, and the next change would be reverting that change. This tabu is defined as follows: 0, case: p=1∧cfix=0 2+cfix2/2-cfix, case: p=1∧cfix=2*k, cfix, k∈ℕ\{0} sw = 1+cfix*(cfix-1)/2, case: p=1∧cfix=2*k-1, k∈ℕ\{0} (1) 1+p2/2-p, case: p>1∧p=2*k, p∈ℕ\{0,1}, k∈ℕ\{0} p*(p-1)/2, case: p>1∧p=2*k-1, p∈ℕ\{0,1}, k∈ℕ\{0} (cfix being the number of fixed candidates within a type of PDO change (i.e. to these candidates can be switched), p being the number of pools of sets of entities (e.g. each source for the properties is a pool like string ranges, Boolean ranges, DBpedia, or WordNet; p can be changed for each type of PDO change in the administration interface); a pool p can be switched on the level of ontological entity ( s’ ) or completely ( s ), i.e. all sets of ontological entities are switched at once (can be changed for each type of PDO change in the administration interface, in case of more than one data pool p), k being a natural number to indicate an even ( cfix = 2 * k, p = 2 * k ) or odd (cfix = 2 * k - 1, p = 2 * k 1 ) number of fixed candidates or pools: The case for the even cfix or p equates to an Eulerian trail, the case for the odd cfix or p to an Eulerian circuit).
Result is the number of allowed switches sw. In case s is already connected to cfix (e.g. s - cfix = 1), the second and third case in (1) are lessen by this one “impossible” switch (i.e. swfix = sw - 1). 4.1.1.2 Allowed Number of Vertical PDO Change Iterations ch With ch successive sw switches within the same type of PDO change are executed, i.e. the next (sets of) ontological entities are going to be switched. This tabu is defined as follows:
(s-chfix)/n; case: p=1, n∈ℕ\{0}, s, chfix∈ℕ, s≥chfix ch = s’/n, case: p>1∧s’⊂s (i.e. single sets), n∈ℕ\{0}, s’∈ℕ (2) Not applicable, case: p>1∧s’≡s (i.e. all sets at once) ch is truncated to the natural number. (s being all sets of ontological entities within a type of PDO change (e.g. all sets of individuals, all sets of properties, all sets of annotation properties label and comment), s’ being a single set of ontological entities within a type of PDO change (e.g. specific properties) to be switched to another pool, n being the fraction of the “free” sets (i.e. not connected to a cfix) of entities within a type of PDO change allowed to be switched (e.g. n = 1: All free sets of entities, n = 2: Half of the free sets, etc.; n can be changed for each type of PDO change in the administration interface)). Result is the number of allowed PDO change iterations ch. Analogous to the case distinction of the horizontal switches sw and swfix, ch is splitted in the first case in (2) into s is not connected to cfix before switching (ch), and s is already connected to cfix before switching (chfix). 4.1.2 General Tabu Criterion gt To avoid an uniform optimisation and cycles, the PDO changes within the same type of PDO change are consecutively executed only as often as there are different types T of PDO changes not induced by a feedback based on a PDO extraction (here: Three times, T = 3, i.e. switching individuals, switching datatype property ranges, and switching annotation properties label and comment).
In case a type of PDO change has less than T PDO changes, the general tabu criterion gt is met when all PDO changes within the respective type of PDO change have been executed.
To calculate the general tabu criterion gt, the overall number of switches sw and ch executed has to be respected. Hence, this tabu is valid when having executed either all sw and ch switches within the respective type of PDO change (case: Number of all switches ≤ T) or the number of switches executed within the same type of PDO change equals T (here: T = 3) (case: Number of all switches > T); this tabu is defined as follows:
sw*ch+(sw-1)*chfix≤T, case: p=1, sw, ch, chfix, T∈ℕ gt = sw*ch≤T, case: p>1∧s’⊂s (i.e. single sets), sw, ch, T∈ℕ (3) sw≤T, case: p>1∧s’≡s (i.e. all sets at once), sw, T∈ℕ Result is the number of allowed PDO changes gt. The PDO changes are sequentially executed and added to the tabu list. In case the tabu gt or T is met, another type of PDO change is going to be executed.
In case another type of PDO change is executed, the overall oldest tabu is deleted from the tabu list.
After the ramp-up and in case the general tabu criterion gt or T is met (here: The same type of PDO change shall be consecutively executed for the fourth time), the PDO change with the highest ST in another type of PDO change is going to be executed and ST(t+1) calculated.
In case the “allowed number of horizontal switches” sw is met, the PDO change with the second highest ST within the same type of PDO change is executed and ST(t+1) calculated. 4.2 Example Calculation of the Tabu Criteria The tabu criteria are exemplarily calculated for the type of PDO change switching individuals. It has one data pool (p = 1, i.e. one set of individuals); p is manually entered in the Administration Interface. A digital camera has the following sets of properties and individuals {s, I}: {faceDetection, Features}, {weight, WeightAndDimension}, {videofunction, GeneralCharacteristics}, {HDMI, Ports}, {opticalZoomFactor, LensFeatures}, and {touchscreen, Display}. So, the question if the camera should offer HDMI is nestled between the port-related features of the camera. By observing the relationships, it is obvious that not all combinations make sense, e.g. HDMI cannot belong to WeightAndDimension, but it could belong to Features or GeneralCharacteristics. When switching the HDMI property to another individual, e.g. from Ports to GeneralCharacteristics, the question after HDMI could be placed aside the question for the video function which could make more sense from a customer point of view. The Feedback Transformer identifies the general individuals (i.e. cfix) by parsing the strings. In the example the two individuals mentioned above are of general meaning, i.e. cfix = 2. •
Specific tabu criterion “allowed number of horizontal switches” sw: (1), second case, with cfix = 2: sw = 2 (case: s is not connected to cfix before switching) and swfix = 1 (case: s is already connected to cfix before switching) Result: The specific tabu criterion sw is met with two switches or one switch; in this case, the next set of individuals is going to be switched.
Specific tabu criterion “allowed number of vertical PDO
change iterations” ch:
4.3 Future Work: Evaluation and Validation
of the Adaptation Layer
The adaptation layer is going to be evaluated by conducting an
experiment with approximately thirty ontology experts who
evaluate the ontology evolution. The automatically evolved PDO
is going to be compared with a manually evolved one by setting
up and evaluating an experiment with ontology experts who
analyse the feedback delivered and decide the PDO changes to be
executed. Eventually, the PDO resulted from this manual
evolution is compared with the automatically evolved one
regarding the evaluation criteria consistency, completeness,
conciseness, expandability, and sensitiveness [
The adaptation layer is going to be validated by programming the layer and measuring the effects in the e-commerce recommender system. Its success is defined by the click-out rate (i.e. clicks-torecommendations; the user follows the recommendation by clicking on the product recommended) which measures the impact of the PDO evolution induced by the implicit and explicit user feedback.
The validation scenario will be to analyse and evaluate the impact of the PDO evolution with regard to the respective KPI reported to the adaptation layer after having accomplished the defined number of recommendation processes by utilising the formulated evolution strategies, i.e. Risky, Progressive, and Safe Evolution. In each feedback cycle the transformed feedback (i.e. ST) gets reported to the Adaptation Manager. The feedback is PDO-based or PDO- and property-based. According to the feedback reported, the PDO evolves. The new PDO version is provided to the data modelling layer and the application layer, and eventually an adapted recommender interface is presented to the customer. The feedback circle of the automated system concludes with reevaluating the KPI after having again accomplished the defined number of recommendation processes.
The intended results are a highly user-adaptive system and
eventually better recommendations given to the customer leading
to an increase of the defined KPI. The expected business impacts
are a higher customer satisfaction and loyalty and eventually
increased revenue for the provider of the e-commerce application
(and the recommender system).
5. CONCLUSION
The need for automatically updating and evolving ontologies is
urging in today’s usage scenarios. Here, it is the basis for creating
a user-adaptive recommender interface. The present research
tackles an automated process for the first time (to the best
knowledge of the author). The reason for that can be found in the
ontology definition “formal, explicit specification of a shared
conceptualisation” [
In this research the PDO are based on GoodRelations and evolve
within that upper ontology. This ontology as well as the
“subsumed” PDO conforms to the ontology definition by [