=Paper=
{{Paper
|id=Vol-1388/PEGOV2015-paper1
|storemode=property
|title=A Wiki-based Environment for Constraint-based Recommender Systems Applied in the E-Government Domain
|pdfUrl=https://ceur-ws.org/Vol-1388/PEGOV2015-paper1.pdf
|volume=Vol-1388
|dblpUrl=https://dblp.org/rec/conf/um/ReitererFJSWE15
}}
==A Wiki-based Environment for Constraint-based Recommender Systems Applied in the E-Government Domain==
https://ceur-ws.org/Vol-1388/PEGOV2015-paper1.pdf
A Wiki-based Environment for Constraint-based
Recommender Systems Applied in the
E-Government Domain
Stefan Reiterer1 , Alexander Felfernig1 , Michael Jeran1 , Martin Stettinger1 ,
Manfred Wundara2 , and Wolfgang Eixelsberger3
1
Institute for Software Technology, A-8010 Graz, Inffeldgasse 16b
firstname.lastname@ist.tugraz.at
2
City of Villach, A-9500 Villach, Rathausplatz 1
manfred.wundara@villach.at
3
Carinthia University of Applied Sciences, A-9524 Villach, Europastraße 4
w.eixelsberger@fh-kaernten.at
Abstract. Constraint-based recommenders support customers in iden-
tifying relevant items from complex item assortments. In this paper we
present WeeVis, a constraint-based environment that can be applied
in different scenarios in the e-government domain. WeeVis supports
collaborative knowledge acquisition for recommender applications in a
MediaWiki-based context. This paper shows how Wiki pages can be ex-
tended with recommender applications and how the environment uses
intelligent mechanisms to support users in identifying the optimal solu-
tions to their needs. An evaluation shows a performance overview with
different knowledge bases.
1 Introduction
Constraint-based recommender applications help users navigating in complex
product and service assortments like digital cameras, computers, financial ser-
vices and municipality services. The calculation of the recommendations is based
on a knowledge base of explicitly defined rules. The engineering of the rules for
recommender knowledge bases (for constraint-based recommenders) is typically
done by knowledge engineers, mostly computer scientists [1]. For building high
quality knowledge bases there are domain experts involved who serve the knowl-
edge engineers with deep domain knowledge [1]. Graphical knowledge engineering
interfaces like [2] improved the maintainability and accessability and moved the
field one step further.
Other recommendation approaches like collaborative filtering use informa-
tion about the rating behavior of other users to identify recommendations [3, 4].
Content-based filtering [5] exploits features of items for the determination of rec-
ommendations. Compared to these approaches, constraint-based recommenders
are more applicable for complex products and services due to their explicit knowl-
edge representation.
2
In the line of Wikipedia4 where users build and maintain Wiki pages col-
laboratively we introduce WeeVis5 . WeeVis is a MediaWiki6 based environ-
ment that exploits the properties of MediaWiki and enables community based
development and maintenance of knowledge bases for constraint-based recom-
menders. WeeVis is freely available as a platform and successfully applied by
four Austrian universities (in lectures about recommender systems), in the fi-
nancial services domain and in e-government .
In the e-government domain officials as well as the community residents can
take numerous advantages of knowledge-based recommenders:
– WeeVis can be used as an online advisory service for citizens for example
for documents that are necessary to apply for a private construction project.
The online recommendation of necessary documents in advance to on-site
appointments can lead to a time reduction for community residents and
community officials.
– WeeVis can be used for modeling internal processes like the signing of travel
applications for example a community official wants to visit a conference,
based on different parameters like the conference type, or if it’s abroad or
in the domestic area, different officials have to sign the travel request. In
WeeVis the appropriate rules for such internal processes can be mapped and
especially for new employees WeeVis recommenders can provide substantial
assistance.
– WeeVis can be used as an information platform for example with integrated
knowledge-based recommenders for community residents e.g. to identify the
optimal waste disposal strategy for a household (this example is used as a
running example in this paper, see Section 2). Instead of providing plain text
information, like common municipality web pages, the knowledge represen-
tation as a recommender provides an easier way for community members to
identify the optimal solution for their situation.
A recommender development environment for single users is introduced in [2].
This work is based on a Java platform and focuses on constraint-based recom-
mender applications for online selling. Compared to [2], WeeVis provides a
wiki-based user interface that allows user communities to develop recommender
applications collaboratively. Instead of an incremental dialog, where the user
answers one question after the other, like [2], WeeVis provides an integrated
interface where the user is free to answer questions in any order.
The WeeVis interface also provides intelligent mechanisms for an instant
presentation of alternative solutions in situations where it is not possible to find
a solution for a given set of user (customer) requirements, i.e., the requirements
are inconsistent with the recommendation knowledge base and the user is in
the need for repair proposals to find a way out from the no solution could be
found dilemma. Model-based diagnosis [6] can be applied for the identification
4
www.wikipedia.org
5
www.weevis.org
6
www.mediawiki.org
3
of faulty constraints in a given set of customer requirements. In this context
efficient divide-and-conquer based algorithms [7] can be applied to the diagnosis
and repair of inconsistent requirements. The environment supports the user with
integrated model-based diagnosis techniques [6,8]. A first approach to a conflict-
directed search for hitting sets in inconsistent CSP definitions was introduced
by [9]. With regard to diagnosis techniques, WeeVis is based on more efficient
techniques that make the environment applicable in interactive settings [8, 10].
A Semantic Wiki-based approach to knowledge acquisition for collaborative
ontology development is introduced, for example, in [11]. Compared to [11],
WeeVis is based on a recommendation domain specific knowledge representa-
tion (in contrast to ontology representation languages) which makes the defini-
tion of domain knowledge more accessible also for domain experts.
The remainder of this paper is organized as follows. In Section 2 we present an
overview of the recommendation environment WeeVis and it’s application in the
e-government domain. In Section 3 we present results of a performance evaluation
that illustrates the performance of the integrated diagnosis technologies. With
Section 4 we conclude the paper.
2 WeeVis Overview
Since WeeVis is based on the MediaWiki platform, it can be installed on freely
available web servers. On the website www.weevis.org a selection of different
WeeVis recommenders is publicly available. For internal processes WeeVis
can be deployed in the local intranet. Standard wiki pages can be complemented
easily by recommender knowledge bases. Currently, WeeVis calculates recom-
mendations based on previously entered requirements. If the requirements would
result in a no solution could be found message Weevis calculates alternative so-
lutions based on diagnoses (see Section 2.4). In line with the Wiki idea, WeeVis
provides the ability to build knowledge bases collaboratively, a valuable feature
in e-government domain, because depending on the community department mul-
tiple people are responsible for data management and administration. Further-
more, WeeVis exploits the basic functionalities provided by MediaWiki and
allows rapid prototyping processes where the result of a change can immediately
be seen by simply switching from the edit mode to the corresponding read mode.
This approach allows an easy understanding of the WeeVis tags and also of the
semantics of the provided WeeVis language.
2.1 WeeVis User Interface
Since WeeVis is a MediaWiki-based environment the user interface relies on the
common Wiki principle of the read mode (see Figure 1) for executing a recom-
mender and the write mode (see Figure 2) for defining a recommender knowledge
base. The development and maintenance of a knowledge base is supported a tex-
tual fashion with a syntax that is similar to the standard Wiki syntax (see Figure
4
Fig. 1. Waste Disposal Strategy a simple recommender knowledge base from the e-
government domain (WeeVis read mode).
2). In the following we will present the concepts integrated in the WeeVis envi-
ronment on the basis of a working example from the e-government domain. More
specifically we present a recommender that supports households in identifying
their optimal waste disposal strategy. In this recommendation scenario, a user
has to specify his/her requirements regarding, for example, the number of per-
sons living in the household or how frequently the containers should be emptied.
A corresponding WeeVis user interface is depicted in Figure 1. Requirements
are specified on the left hand side and the corresponding recommendations for
the optimal waste disposal plan are displayed in the right hand side.
For each solution, a so-called support score is determined. If a solution fulfills
all requirements, this score is 100%, otherwise it is lower and, when clicking
on the score value, a corresponding repair action is displayed on the left-hand
side (see Figure 1). Due to the automated alternative determination, WeeVis
is always able to present a solution and users are never ending up in the no
solution could be found dilemma (see Figure 1).
An example of the definition of a (simplified) e-government recommender
knowledge base is depicted in Figure 2. The definition of a recommender knowl-
edge base is supported in a textual fashion on the basis of a syntax similar to
MediaWiki. Basic syntactical elements provided in WeeVis will be introduced
in the next subsection.
2.2 WeeVis Syntax
A WeeVis recommender consists of three necessary aspects, the definition of
questions and possible answers, items and their properties, and constraints (see
Figure 2).
5
Fig. 2. The Waste Disposal Strategy recommender knowledge base (view source (edit)
mode).
The definition of an item assortment in WeeVis starts with the &PROD-
UCTS tag (see Figure 2). The first line represents the attributes separated by
the exclamation mark. In our example, the item assortment is specified by the
name, sizep, the container size, emptyingp, the emptying frequency, and pricep,
the price of the waste disposal plan. Each of the next lines represents an item
with the values related to the attributes, in our example there are three items
specified: Small Plan, Medium Plan, and Large Plan.
The second aspect starts with the &QUESTIONS tag. In our example the
following user requirements are defined: persons, specifies the number of persons
living in the household (one to two, three to four, more than four) and maxprice
specifies the upper limit regarding the price of the waste disposal plan. Further-
more, emptying represents the sequence in which the dustbins will be emptied,
weekly or monthly, and container size, the preferred size of the dust container,
120 or 60.
The third aspect represents the definition of the constraints. Starting with
the &CONSTRAINTS tag in WeeVis different types of constraints can be de-
fined. For the first constraint in our example the &INCOMPATIBLE keyword is
used to describe incompatible combinations of requirements. The first incompat-
ibility constraint describes an incompatibility between the number of persons in
the household (persons) and the container size. For example, a waste disposal
6
plan with (container size) 60 must not be recommended to users who live in a
household with more than four persons. Filter constraints describe relationships
between requirements and items, for example, maxprice ≥ pricep, i.e., the price
of a waste disposal plan must be equal or below the maximum accepted price.
2.3 Recommender Knowledge Base
A recommendation knowledge base can be represented as a CSP (Constraint
Satisfaction Problem) [12] on a formal level. The CSP has two sets of variables
V (V = U ∪ P ) and the constraints C = P ROD ∪ COM P ∪ F ILT where ui ∈ U
are variables describing possible user requirements (e.g., persons) and pi ∈ P are
describing item properties (e.g., emptyingp). Each variable vi has a domain dj
of values that can be assigned to the variable (e.g., one to two, three to four or
more than four for the variable persons). Furthermore, there are three different
types of constraints:
– COM P represents incompatibility constraints of the form ¬X ∨ ¬Y
– P ROD the products with their attributes in disjunctive normal form (each
product is described as a conjunction of individual product properties)
– F ILT the given filter constraints of the form X → Y
The knowledge base specified in Figure 2 can be transformed into a constraint
satisfaction problem where &QUESTIONS represents U , &PRODUCTS repre-
sents P and &CONSTRAINTS represents P ROD, COM P , and F ILT . Based
on this knowledge representation WeeVis is able to determine recommenda-
tions that take into account a specified set of user requirements. The results
collected are represented as unary constraints (R = {r1 , r2 , ..., rk }). Finally the
determined set of solutions (recommended items) is presented to the user.
2.4 Diagnosis and Repair of Requirements
In situations where requirements ri ∈ R (unary constraints defined on variables
of U such as emptying = monthly) are inconsistent with the constraints in C,
we are interested in a subset of these requirements that should be adapted to be
able to restore consistency. On a formal level we define a requirements diagnosis
task and a corresponding diagnosis (see Definition 1).
Definition 1 (Requirements Diagnosis Task). Given a set of requirements R
and a set of constraints C (the recommendation knowledge base), the require-
ments diagnosis task is to identify a minimal set ∆ of constraints (the diagnosis)
that has to be removed from R such that R − ∆ ∪ C is consistent.
As an example R = {r1 : persons = morethanf our, r2 : maxprice = 600,
r3 : emptying = monthly, r4 : containersize = 60} is a set of requirements
inconsistent with the defined recommendation knowledge. The recommendation
knowledge base induces two minimal conflict sets (CS) [7] in R which are CS1 :
{r1 , r4 } and CS2 : {r1 , r3 }. For these requirements we can derive two diagnoses:
∆1 : {r3 , r4 } and ∆2 : {r1 }. For example, to achieve consistency of ∆1 at least
7
r3 and r4 have to be adapted. Such diagnoses can be determined on the basis of
a HSDAG (hitting set directed acyclic graph) (e.g. [13]).
Determining conflict sets [7] at first and afterwards constructing a HSDAG
(hitting set directed acyclic graph) to identify diagnoses tends to become inef-
ficient especially in interactive settings. Direct diagnosis algorithms like Fast-
Diag [8] reduce this two-step process to one step by calculating diagnoses di-
rectly without conflict determination. This was the major motivation for inte-
grating FastDiag [8] into the WeeVis environment. Like QuickXPlain [7],
FastDiag is based on a divide-and-conquer approach that enables the calcula-
tion of minimal diagnoses without the calculation of conflict sets. In WeeVis
the derived diagnosis are used as a basis for determining repair actions, which
lead to the alternative solutions that are be presented to the user. A repair ac-
tion is a concrete change of one or more user requirements in R on the basis of
a diagnosis such that the resulting R0 is consistent with C.
Definition 2 (Repair Task). Given a set of requirements R = {r1 , r2 , ..., rk }
inconsistent with the constraints in C and a corresponding diagnosis ∆ ⊆ R
(∆ = {rl , ..., ro }), the corresponding repair task is to determine an adaption
A = {rl0 , ..., ro0 } such that R − ∆ ∪ A is consistent with C.
In WeeVis, repair actions are determined conform to Definition 2. For each
diagnosis ∆ determined by FastDiag, the corresponding solution search for
R − ∆ ∪ C returns a set of alternative repair actions (represented as adaptation
A). In the following, all solutions that satisfy R − ∆ ∪ A are shown to the user
(see the right hand side of Figure 1).
Diagnosis determination in FastDiag is based on a total lexicographical
ordering of the customer requirements [8]. This ordering is derived from the se-
quence of the entered requirements. For example, if r1 : persons = morethanf our
has been entered before r3 : emptying = monthly and r4 : containersize = 60
then the underlying assumption is that r3 and r4 are of lower importance for
the user and thus have a higher probability of being part of a diagnosis. In our
working example ∆1 = {r3 , r4 }. The corresponding repair actions (solutions for
R − ∆1 ∪ C) is A = {r30 : emptying = weekly, r40 : containersize = 120}, i.e.,
{r1 , r2 , r3 , r4 }−{r3 , r4 }∪{r30 , r40 } is consistent. The item that satisfies R−∆1 ∪A
is {LargeP lan} (see in Figure 2). The identified items (p) are ranked according
to their support value (see Formula 1).
#adaptions in A
support(p) = (1)
#requirements in R
3 Performance Evaluation
3.1 Description of the evaluation
We have conducted a performance evaluation with the goal to highlight the abil-
ity of WeeVis to calculate repair actions and if no solutions could be found.
Therefore we set up an experiment with three WeeVis recommenders based
8
on the e-government example presented in Section 2. To illustrate the perfor-
mance of WeeVis, the knowledge base was extended and deployed with differ-
ent complexity regarding the number of solutions (&PRODUCTS tag in Wee-
Vis), user requirements (&QUESTIONS tag WeeVis), and constraints (&CON-
STRAINTS tag WeeVis) (see Table 1). According to these three attributes the
knowledge bases were classified as Small, Medium, and Large. To fit the at-
tributes of knowledge base Small from Table 1, the running example (see Figure
2) was adapted by adding one question, two products and removing the last two
constraints. The Medium and Large knowledge base are extended versions of the
running example.
Knowledge base Number of solutions /
requirements / constraints
Small 5/5/5
Medium 20/10/15
Large 50/15/30
Table 1. The different knowledge bases with sizes Small, Medium and Large used for
the performance comparison.
3.2 Results of the evaluation
To provide an optimal user experience a focus of WeeVis is to provide instant
feedback after every interaction. Interacting with a WeeVis recommender starts
with the the entering of new requirements and the subsequent calculation of so-
lutions for these requirements. If no solution could be found WeeVis calculates
one or more diagnoses and the complementing alternative products. With this
performance evaluation we show that WeeVis can identify at least one alterna-
tive solution even for large knowledge bases within recommended user interface
response times [14]:
– below 100ms, the user feels that the system reacts instantaneously
– 1,000ms is the upper limit for keeping the users thought uninterrupted
– 10,000ms is the upper limit for keeping the user’s focus on the dialogue
For the first performance evaluation the goal was to measure the time needed
for calculating the corresponding solutions to given requirements. After assigning
answers to the questions for the three different knowledge bases, the resulting
values are depicted in Table 2. The performance values in Table 2 show that for
each of the knowledge bases WeeVis identifies solutions fast enough to provide
instantaneous feedback from the user interface. If no solution could be found
due to inconsistencies between the requirements and the knowledge base, Table
3 shows the time needed to identify at least one alternative solution on the basis
of one preferred diagnosis, Table 4 shows the time consumption of calculating
9
all possible solutions. WeeVis is able to calculate either one, two, three or all
diagnoses and the corresponding alternative solutions. By taking the response
time boundaries for user interfaces into account, the experiment shows that
for small and medium knowledge bases it’s possible to calculate all minimal
diagnoses within acceptable response times (see Table 3). When it comes to large
knowledge bases the presented alternative solutions can be reduced to increase
the performance of the user interface instead (see Table 4).
time for identifying solutions
Small < 1ms
Medium < 1ms
Large < 2ms
Table 2. This table shows the time needed to come up with solutions for three knowl-
edge bases. Even for the largest knowledge base the overall time is far below the limit
of an instantaneously reaction(100ms).
diagnosis repair overall time
calculation identification
Small < 1ms < 1ms < 1ms
Medium 93ms 16ms 109ms
Large 499ms 19ms 518ms
Table 3. This table shows the time needed to come up with at least one alternative
solution for each of the three knowledge bases. Even for the largest knowledge base the
overall time is below the limit of interrupt a users thought (1,000ms).
diagnosis repair overall time
calculation identification
Small 97ms 16ms 113ms
Medium 969ms 20ms 989ms
Large 3, 028ms 60ms 3, 088ms
Table 4. This table shows the time needed to come up with all possible alternative so-
lutions for each of the three knowledge bases. For the largest knowledge base the overall
time for repair calculation takes about three seconds which is above the recommended
time boundaries for interrupting the user’s flow of thought.
10
4 Conclusion
In this paper we presented WeeVis which is an open constraint-based recom-
mendation environment. By exploiting the advantages of Mediawiki, WeeVis
provides an intuitive basis for the development and maintenance of constraint-
based recommender applications. The results of our experiment show that due
to the integrated direct diagnosis algorithms the WeeVis user interface provides
good the response times for common interactive settings.
References
1. A. Felfernig and R. Burke. Constraint-based Recommender Systems: Technologies
and Research Issues. In 10th International Conference on Electronic Commerce,
page 3. ACM, 2008.
2. A. Felfernig, G. Friedrich, D. Jannach, and M. Zanker. An Integrated Environ-
ment for the Development of Knowledge-based Recommender Applications. Inter-
national Journal of Electronic Commerce, 11(2):11–34, 2006.
3. G. Linden, B. Smith, and J. York. Amazon. com recommendations: Item-to-item
collaborative filtering. Internet Computing, IEEE, 7(1):76–80, 2003.
4. J. Konstan, B. Miller, D. Maltz, J. Herlocker, L. Gordon, and J. Riedl. GroupLens:
Applying Collaborative Filtering to Usenet News. Communications of the ACM,
40(3):77–87, 1997.
5. M. Pazzani and D. Billsus. Learning and Revising User Profiles: The Identification
of Interesting Web Sites. Machine learning, 27(3):313–331, 1997.
6. R. Reiter. A Theory of Diagnosis From First Principles. Artificial intelligence,
32(1):57–95, 1987.
7. U. Junker. QUICKXPLAIN: Preferred Explanations and Relaxations for Over-
constrained Problems. In Proceedings of the 19th National Conference on Artifical
Intelligence (AAAI’04), pages 167–172, 2004.
8. A. Felfernig, M. Schubert, and C. Zehentner. An Efficient Diagnosis Algorithm
for Inconsistent Constraint Sets. Artificial Intelligence for Engineering Design,
Analysis and Manufacturing, 26:53–62, 2012.
9. R. Bakker, F. Dikker, F. Tempelman, and P. Wogmim. Diagnosing and Solving
Over-determined Constraint Satisfaction Problems. In 13th International Joint
Conference on Artificial Intelligence, pages 276–281, Chambery, France, 1993.
10. G. Friedrich. Interactive Debugging of Knowledge Bases. In International Work-
shop on Principles of Diagnosis (DX’14), pages 1–4, Graz, Austria, 2014.
11. J. Baumeister, J. Reutelshoefer, and F. Puppe. KnowWE: a Semantic Wiki for
Knowledge Engineering. Applied Intelligence, 35(3):323–344, 2011.
12. A. Mackworth. Consistency in Networks of Relations. Artificial Intelligence,
8(1):99–118, 1977.
13. A. Felfernig, G. Friedrich, D. Jannach, and M. Stumptner. Consistency-based
Diagnosis of Configuration Knowledge Bases. Artificial Intelligence, 152(2):213–
234, 2004.
14. J. Nielsen. Usability engineering. Elsevier, 1994.