=Paper=
{{Paper
|id=Vol-1349/paper2
|storemode=property
|title=Conflict Management in Interactive Financial Service Selection
|pdfUrl=https://ceur-ws.org/Vol-1349/paper02.pdf
|volume=Vol-1349
|dblpUrl=https://dblp.org/rec/conf/finrec/FelfernigS15
}}
==Conflict Management in Interactive Financial Service Selection==
https://ceur-ws.org/Vol-1349/paper02.pdf
Conflict Management in
Interactive Financial Service Selection
Alexander Felfernig1 and Martin Stettinger1
Abstract. Knowledge-based systems are often used to support this paper we will focus on the application of the concepts of model-
search and navigation in a set of financial services. In a typical pro- based diagnosis [27, 5]. A first application of model-based diagnosis
cess users are defining their requirements and the system selects and to the automated identification of erroneous constraints in knowl-
ranks alternatives that seem to be appropriate. In such scenarios sit- edge bases is reported in Bakker et al. [1]. In their work the au-
uations can occur in which requirements can not be fulfilled and al- thors show how to model the task of identifying faulty constraints
ternatives (repairs) must be proposed to the user. In this paper we in a knowledge base as a diagnosis task. Felfernig et al. [8] extend
provide an overview of model-based diagnosis techniques that can the approach of Bakker et al. [1] by introducing concepts that al-
be applied to indicate ways out from such a ”no solution could be low the automated debugging of (configuration) knowledge bases
found” dilemma. In this context we focus on scenarios from the do- on the basis of test cases. If one or more test cases fail within the
main of financial services. scope of regression testing, a diagnosis process is activated that de-
termines a minimal set of constraints in such a way that the deletion
of these constraints guarantees that each test case is consistent with
1 Introduction
the knowledge base. Model-based diagnosis [27] relies on the exis-
Knowledge-based systems such as recommenders [2, 18] and config- tence of conflict sets which represent minimal sets of inconsistent
urators [6, 9, 28] are often used to support users (customers) who are constraints. Conflict sets can be determined by conflict detection al-
searching for solutions fitting their wishes and needs. These systems gorithms such as Q UICK XP LAIN [19].
select and also rank alternatives of relevance for the user. Examples Beside the automated testing and debugging of inconsistent
of such applications are knowledge based recommenders that support knowledge bases, model-based diagnosis is also applied in situations
users in the identification of relevant financial services [10, 11] and where the knowledge base per se is consistent but a set of customer
configurators that actively support service configuration [12, 20]. requirements induces an inconsistency. Felfernig et al. [8] also sketch
The mentioned systems have the potential to improve the under- an approach to the application of model-based diagnosis to the iden-
lying business processes, for example, by reducing error rates in the tification of minimal sets of fault requirements. Their approach is
context of order recording and by reducing time efforts related to based on breadth-first search that uses diagnosis cardinality as the
customer advisory. Furthermore, customer domain knowledge can only ranking criteria.
be improved by recommendation and configuration technologies; A couple of different approaches to the determination of person-
through the interaction with these systems customers gain a deeper alized diagnoses for inconsistent requirements have been proposed.
understanding of the product domain and – as a direct consequence DeKleer [4] introduces concepts for the probability-based identifica-
– less efforts are triggered that are related to the explanation of basic tion of leading diagnoses. O’Sullivan et al. [25] introduce the concept
domain aspects. For a detailed overview of the advantages of apply- of representative explanations (diagnosis sets) where each existing
ing such technologies we refer the reader to [9]. diagnosis element is contained in at least one diagnosis of a repre-
When interacting with knowledge-based systems, situations can sentative set of diagnoses. Felfernig et al. [13] show how to integrate
occur where no recommendation or configuration can be identified. basic recommendation algorithms into diagnosis search and with this
In order to avoid inefficient manual adaptations of requirements, to increase the prediction quality (in terms of precision) of diagnos-
techniques can be applied which automatically determine repair ac- tic approaches. Felfernig et al. [14] extend this work and compare
tions that allow to recover from an inconsistency. For example, if different personalization approaches with regard to their prediction
a customer is interested in financial services with high return rates quality and the basis of real-world datasets. Based on the concepts of
but at the same time does not accept risks related to investments, no Q UICK XP LAIN, Felfernig et al. [15] introduced FAST D IAG which
corresponding solution will be identified. improves the efficiency of diagnosis search by omitting the calcuala-
There are quite different approaches to deal with the so-called no tion of conflicts as a basis for diagnosis calculation. This diagnostic
solution could be found dilemma – see Table 1. In the context of approach is also denoted as direct diagnosis [17]. The applicability
1 of FAST D IAG has also been shown in SAT solving scenarios [23].
Applied Software Engineering, Institute for Software Technology,
Graz University of Technology, Austria, email: {felfernig, stet- Different types of knowledge-based systems have already been
tinger}@ist.tugraz.at. applied to support the interactive selection and configuration of fi-
Topic Reference
Reiter 1987 [27], DeKleer
Foundations of model-based diagnosis
et al. 1992 [5]
Conflict detection and model-based diagnosis of inconsistent
Bakker et al. 1993 [1]
constraint satisfaction problems (CSPs)
Regression testing and automated debugging of configuration
Felfernig et al. 2004 [8]
knowledge bases using model-based diagnosis (breadth-first search)
Identification of minimal diagnoses for user requirements for the
purpose of consistency preservation (breadth-first search)
Identification of preferred minimal conflict sets on the basis of a
Junker 2004 [19]
divide-and-conquer based algorithm (Q UICK XP LAIN)
Identification of representative explanations (each existing diagnosis
O’Sullivan et al. 2007 [25]
element is contained in at least one diagnosis of the result set)
Identification of personalized diagnoses on the basis of Felfernig et al. 2009,2013
recommendation algorithms [13, 14]
Probability based identification of leading diagnoses DeKleer 1990 [4]
Identification of preferred minimal diagnoses on the basis of a
Felfernig et al. 2012 [15]
divide-and-conquer based algorithm (FAST D IAG)
Marques-Silva et al. 2013
Preferred minimal diagnoses for SAT based knowledge representations
[23]
Table 1. Overview of research related to conflict management in knowledge-based systems.
nancial services. Fano and Kurth [7] introduce an approach to the tions where (personalized) solutions are determined on the basis of
visualization and planning of financial service portfolios. The simu- conjunctive queries [13]. In Section 5 we provide one further exam-
lation is based on an integrated model of a human’s household and ple of consistency management in the loan domain. In Section 6 we
interdependencies between different financial decisions. Felfernig et discuss issues for future work. With Section 7 we conclude the paper.
al. [10, 11] show how to apply knowledge-based recommender ap-
plications for supporting sales representatives in their dialogs with
customers. Major improvements that can be expected from such an 2 Constraint-based Representations
approach are less errors in the offer phase and more time for ad-
Constraint Satisfaction Problems (CSPs) [16, 22] are successfully
ditional customer meetings. An approach to apply the concepts of
applied in many industrial scenarios such as scheduling [26], con-
cased-based reasoning [21] for the purpose of recommending finan-
figuration [9], and recommender systems [18]. The popularity of this
cial services is introduced by Musto et al. [24].
type of knowledge representation can be explained by the small set
The major focus of this paper is to provide an overview of tech-
of representation concepts (only variables, related domains, and con-
niques that help to recover from inconsistent situations in an auto-
straints have to be defined) and the still high degree of expressivity.
mated fashion. In this context we show how inconsistencies can be
Definition 1 (Constraint Satisfaction Problem (CSP) and Solu-
identified and resolved. The major contributions of this paper are the
tion). A constraint satisfaction problem (CSP) can be defined as a
following: (1) we provide an overview of error identification and re-
triple (V, D, C) where V = {v1 , v2 , ..., vn } represents a set of vari-
pair techniques in the context of financial services recommendation
ables, dom(v1 ), dom(v2 ), ..., dom(vn ) represents the correspond-
and configuration. (2) We show how diagnosis and repair techniques
ing variable domains, and C = {c1 , c2 , ..., cm } represents a set of
can be applied on the basis of different knowledge representations
constraints that refer to corresponding variables and reduce the num-
(CSPs as well as table-based representations). (3) We provide an out-
ber of potential solutions. A solution for a CSP is defined by an as-
look of major issues for future work.
signment A of all variables in V where A is consistent with the con-
The remainder of this paper is organized as follows. In Section
straints in C.
2 we introduce basic definitions of a constraint satisfaction problem
Usually, user requirements are interpreted as constraints
(CSP) and a corresponding solution. On the basis of these defini-
CREQ = {r1 , r2 , ..., rq } where ri represent individual user re-
tions we introduce a first working example from the financial ser-
quirements. In this paper we assume that the constraints in C are
vices domain. Thereafter (in Section 3) we introduce a basic defi-
consistent and inconsistencies are always induced by the constraints
nition of a diagnosis task and show how diagnoses and repairs for
in CREQ. If such a situation occurs, we are interested in the ele-
inconsistent user requirements can be determined. In Section 4 we
ments of CREQ which are responsible for the given inconsistency.
switch from constraint-based to table-based knowledge representa-
On the basis of a first example we will now provide an overview of
diagnosis techniques that can be used to recover from such incon- of HSDAG construction (an example is depicted in Figure 1). In the
sistent situations. An example of a CSP in the domain of financial context of our example of C and CREQ, a first minimal conflict set
services is the following. For simplicity we assume that each vari- that could be returned by an algorithm such as Q UICK XP LAIN [19]
able has the domain {low, medium, high}. is CS1 : {r1 , r3 }.
• V = {av, wr, rr}
• dom(av) = dom(wr) = dom(rr) = {low, medium, high}
• C = {c1 : ¬(av = high∧wr = high), c2 : ¬(wr = low∧rr =
high), c3 : ¬(rr = high ∧ av = high)}
An overview of the variables of this CSP is given in Table 2.
variable description ri ∈ CREQ
av availability r1 : av = high
wr willingness to take risks r2 : wr = low
rr expected return rate r3 : rr = high
Figure 1. Hitting Set Directed Acyclic Graph (HSDAG) for requirements
CREQ = {r1 : av = high, r2 : wr = low, r3 : rr = high}.
Table 2. Overview of variables used in the example CSP definition.
In addition to this basic CSP definition we introduce an example
set of customer requirements CREQ = {r1 : av = high, r2 : wr = There are two possibilities of resolving CS1 , either by delet-
low, r3 : rr = high} which is inconsistent with the constraints ing requirement r1 or by deleting requirement r3 . If we delete r3
defined in C. On the basis of this simplified financial service knowl- (see Figure 1), we managed to identify the first minimal diagnosis
edge base defined as a CSP we will now show how inconsistencies ∆1 = {r3 } which is also a minimal cardinality diagnosis. The sec-
induced by customer requirements can be identified and resolved. ond option to resolve CS1 is to delete r1 . In this situation, another
conflict exists in CREQ, i.e., a conflict detection algorithm would
return CS2 : {r2 , r3 }. Again, there are two possibilities to resolve
3 Diagnosis & Repair of Inconsistent Constraints the conflict (either by deleting r2 or by deleting r3 ). Deleting r3 leads
In our working example, the requirements CREQ and the set of to a diagnosis which is not minimal since {r3 } itself is already a di-
constraints C are inconsistent, i.e., inconsistent(CREQ ∪ C). In agnosis. Deleting r2 leads to the second minimal diagnosis which is
such situations we are interested in a minimal set of requirements ∆2 = {r1 , r2 }.
that have to be deleted or adapted such that consistency is restored. The diagnoses ∆1 and ∆2 are indicators of minimal changes that
Consistency resolution is in many cases based on the resolution of need to be performed on the existing set of requirements such that
conflicts. In our case, a minimal conflict is represented by a minimal a consistency between CREQ and C can be restored. The issue of
set of requirements in CREQ that have to be deleted or adapted such finding concrete repair actions for the requirements contained in a
that consistency can be restored. diagnosis will be discussed later in this paper.
Definition 2 (Conflict Set). A conflict set CS is a subset of CREQ There can be quite many alternative diagnoses. In this context it
s.t. inconsistent (CS ∪ C). A conflict set is minimal if there does is not always clear which diagnosis should be selected or in which
not exist another conflict set CS 0 with CS 0 ⊂ CS. A minimal car- order alternative diagnoses should be shown to the user. In the fol-
dinality conflict set CS is a minimal conflict set with the additional lowing we present one approach to rank diagnoses. The approach we
property that there does not exist another minimal conflict CS 0 with sketch is based on multi-attribute utility theory [29] where we assume
|CS 0 | < |CS|. that customers provide weights for each individual requirement. In
Minimal conflict sets can be determined on the basis of con- the example depicted in Table 3, two customers specified their pref-
flict detection algorithms such as Q UICK XP LAIN [19]. They can be erences in terms of weights for each requirement. For example, cus-
used to derive diagnoses. In our case, a diagnosis ∆ represents a tomer 1 specified a weight of 0.7 for the requirement r3 : rr = high,
set of requirements that have to be deleted from CREQ such that i.e., the attribute rr is of highest importance for the customer. These
C ∪ (CREQ − ∆) is consistent, i.e., diagnoses help to restore the weights can be exploited for ranking a set of diagnoses.
consistency between CREQ and C. Formula 1 can be used for determining the overall importance
Definition 3 (Diagnosis Task and Diagnosis). A diagnosis task can (imp) of a set of requirements (RS). The higher the importance the
be defined as a tuple (C, CREQ) where C represents a set of con- lower the probability that these requirements are element of a diag-
straints in the knowledge base and CREQ represents a set of cus- nosis shown to the customer. Requirement r3 has a high importance
tomer requirements. ∆ is a diagnosis if CREQ−∆∪C is consistent. for customer 1, consequently, the probability that r3 is contained in
A diagnosis ∆ is minimal if there does not exist a diagnosis ∆0 with a diagnosis shown to customer 1 is low.
∆0 ⊂ ∆. Furthermore, ∆ is a minimal cardinality diagnosis if there
does not exist a diagnosis ∆0 with |∆0 | < |∆|.
imp(RS) = importance(RS) = Σr∈RS weight(r) (1)
A standard approach to the determination of diagnoses is based on
the construction of a hitting set directed acyclic graph (HSDAG) [27] Formula 2 can be used to determine the relevance of a partial or
where minimal conflict sets are successively resolved in the process complete (minimal) diagnosis, i.e., this formula can be used to rank
customer weight(r1 : av = high) weight(r2 : wr = low) weight(r3 : rr = high)
1 0.1 0.2 0.7
2 0.3 0.5 0.2
Table 3. Individual weights regarding the importance of the requirements CREQ ={r1 , r2 , r3 }.
diagnoses with regard to their relevance for the customer. The higher
the relevance of a diagnosis, the higher the ranking of the diagnosis
in a list of diagnoses shown to the customer.
1
rel(∆) = relevance(∆) = (2)
importance(∆)
Tables 4 and 5 show the results of applying Formulae 1 and 2 to
the customer preferences (weights) shown in Table 3. For customer
1 (see Table 4), diagnosis ∆2 = {r1 , r2 } has the highest relevance.
For customer 2 (see Table 5), diagnosis ∆1 = {r3 } has the highest
relevance. Consequently, diagnosis ∆2 is the first one that will be
shown to customer 1 and diagnosis ∆1 is the first one that will be Figure 3. FAST D IAG approach to diagnosis determination. CREQ
shown to customer 2. represents a set of customer requirements and C represents a set of
constraints. The algorithm is based on a divide-and-conquer approach: if
diagnosis ∆j importance(∆j ) relevance(∆j ) {r1 , r2 , ..., rk/2 } is consistent with C then diagnosis search can be
∆1 : {r3 } 0.7 1.43 continued in {rk/2+1 ...rk }. ∆ is a diagnosis if CREQ − ∆ ∪ C is
∆2 : {r1 , r2 } 0.3 3.33 consistent.
Table 4. Diagnosis with highest relevance (rel) determined for customer 1:
∆2 = {r1 , r2 }. The afore discussed approaches to diagnosis determination are
based on the construction of a HSDAG [27]. Due to the fact that con-
flicts have to determined explicitly when following this approach, di-
diagnosis ∆j importance(∆j ) relevance(∆j ) agnosis determination does not scale well [13, 14]. The FAST D IAG
∆1 : {r3 } 0.2 5.0 algorithm [15] tackles this challenge by determining minimal and
∆2 : {r1 , r2 } 0.8 1.25 preferred diagnoses without the need of conflict detection. This al-
gorithm has shown to have the same predictive quality as HSDAG
Table 5. Diagnosis with highest relevance (rel) determined for customer 2: based algorithms that determine diagnoses in a breadth-first search
∆1 = {r3 }. regime. The major advantage of FAST D IAG is a high-performance
diagnosis search for the leading diagnoses (first-n diagnoses).
FAST D IAG is based on the principle of divide and conquer – see
Figure 3: if a set of requirements CREQ is inconsistent with a cor-
responding set of constraints C and the first part {r1 , r2 , ..., rk/2 }
of CREQ is consistent with C then diagnosis search can focus on
{rk/2+1 , ..., rk }, i.e., can omit the requirements in {r1 , r2 , ..., rk/2 }.
A detailed discussion of FAST D IAG can be found in [15].
Determination of Repair Actions. Repair actions for diagnosis el-
ements can be interpreted as changes to the originial set of require-
ments in CREQ in such a way that at least one solution can be
identified. If we assume that CREQ is a set of unary constraints that
Figure 2. Personalized diagnosis determined for CREQ and the are inconsistent with C and ∆ is a corresponding diagnosis, then a
individual importance weights defined in Table 3 (for customer1). In this
set of repair actions R = {a1 , a2 , ..., al } can be identified by the con-
example, ∆2 is the preferred diagnosis since
relevance(∆2 ) > relevance(∆1 ). sistency check CREQ − ∆ ∪ C where aj (a variable assignment)
is a repair for the constraint rj if rj is in ∆.
In this section we took a look at different approaches that support
On the basis of the relevance values depicted in Table 4, Figure 2 the determination of diagnoses in situations where a given set of re-
depicts a HSDAG [27] with additional annotations regarding diagno- quirements becomes inconsistent with the constraints in C. In the
sis relevance (rel). The higher the relevance of a (partial) diagnosis, following we will take a look at an alternative knowledge representa-
the higher the ranking of the corresponding diagnosis. tion where tables (instead of CSPs) are used to represent knowledge
id return rate p.a. (rr) runtime in yrs. (rt) risk level (wtr) shares percentage (sp) acessibility (acc) bluechip(bc)
1 4.2 3.0 A 0.0 no yes
2 4.7 3.7 B 10.0 yes yes
3 4.8 3.5 A 10.0 yes yes
4 5.2 4.0 B 20.0 yes no
5 4.3 3.5 A 0.0 yes yes
6 5.6 5.0 C 30.0 no no
7 6.7 6.0 C 50.0 yes no
8 7.9 7.0 C 50.0 no no
Table 6. Investment products: return rate p.a. (rr), runtime in years (rt), risk level (wtr), shares percentage (sp), accessibility (acc), and bluechip (bc).
customer weight(r1 : rr ≥ 5.5) weight(r2 : rt = 3.0) weight(r3 : acc = yes) weight(r4 : bc = yes)
1 0.7 0.1 0.1 0.1
2 0.1 0.7 0.1 0.1
Table 7. Individual weights regarding the importance of the requirements CREQ ={r1 , r2 , r3 , r4 }.
about financial services. Again, we will show how to deal with in- ∆ is a diagnosis if σ[CREQ−∆] T returns at least one solution. Mini-
consistent situations. mality properties of diagnoses are the same as in Definition 3.
The requirements rj ∈ CREQ are inconsistent with the items
included in T (see Table 6), i.e., there does not exist a finan-
4 Table-based Representations cial service in T that completely fulfills the user requirements in
CREQ. Minimal conflict sets that can be derived for CREQ =
In Section 3 we analyzed different ways of diagnosing inconsistent {r1 : rr ≥ 5.5, r2 : rt = 3.0, r3 : acc = yes, r4 : bc = yes}
CSPs [16, 22]. We now show how diagnosis can be performed on are CS1 : {r1 , r2 }, CS2 : {r2 , r3 }, and CS3 : {r1 , r4 }. The deter-
a predefined set of solutions, i.e., a table-based representation. Ta- mination of the corresponding diagnoses is depicted in Figure 4.
ble 6 includes an example set of investment products. The set of
financial services {1, 2, ..., 8} is stored in an item table T [13] –
T can be interpreted as an explicit enumeration of the possible so-
lutions (defined by the set C in Section 2). Furthermore, we as-
sume that the customer has specified a set of requirements CREQ
= {r1 : rr ≥ 5.5, r2 : rt = 3.0, r3 : acc = yes, r4 : bc = yes}.
The existence of a financial service in T that is able to fulfill all re-
quirements can be checked by a relational query σ[CREQ] T where
CREQ represents a set of selection criteria and T represents the
corresponding product table.
An example query on the product table T could be σ[rr≥5.5] T Figure 4. Hitting Set Directed Acyclic Graph (HSDAG) for requirements
which would return the financial services {6,7,8}. For the query CREQ = {r1 : rr ≥ 5.5, r2 : rt = 3.0, r3 : acc = yes, r4 : bc = yes}.
σ[r1 ,r2 ,r3 ,r4 ] T there does not exist a solution. In such situations we
are interested in finding diagnoses that indicate minimal sets of re-
quirements in CREQ that have to be deleted or adapted in order to Diagnoses are determined in the same fashion as discussed in
be able to identify a solution. Section 2. Minimal diagnoses that can be derived from the conflict
Definition 4 (Conflict Sets in Table-based Representations). A con- sets CS1 , CS2 , and CS3 are ∆1 : {r1 , r2 }, ∆2 : {r1 , r3 } and
flict set CS is a subset of CREQ s.t. σ[CS] T returns an empty result ∆3 : {r2 , r4 } (see Figure 4).
set. Minimality properties of conflict sets are the same as introduced Again, the question arises which of the diagnoses has the high-
in Definition 2. est relevance for the user (customer). Table 7 depicts the importance
A diagnosis task and a corresponding diagnosis in the context of distributions for the requirements of our example. Based on the im-
table-based representations can be defined as follows. portance distributions depicted in Table 7 we can derive a preferred
Definition 5 (Diagnosis in Table-based Representations). A diag- diagnosis (see Figure 5). Diagnosis ∆3 will be first shown to cus-
nosis task can be defined as a tuple (T, CREQ) where T represents a tomer 1 since ∆3 has the highest evaluation in terms of relevance
product table and CREQ represents a set of customer requirements. (see Formula 2). The first diagnosis shown to customer 2 is ∆2 .
Figure 5. Personalized diagnoses determined for CREQ and the individual importance weights defined in Table 7 (for customer 1). In this example, ∆3 is
the preferred diagnosis.
diagnosis ∆j importance(∆j ) relevance(∆j )
∆1 : {r1 , r2 } 0.8 1.25
∆2 : {r1 , r3 } 0.8 1.25
∆3 : {r2 , r4 } 0.2 5.0
Table 8. Diagnosis with highest relevance (rel) determined for customer 1: ∆3 = {r2 , r4 }.
diagnosis ∆j importance(∆j ) relevance(∆j )
∆1 : {r1 , r2 } 0.8 1.25
∆2 : {r1 , r3 } 0.2 5.0
∆3 : {r2 , r4 } 0.8 1.25
Table 9. Diagnosis with highest relevance (rel) determined for customer 2: ∆2 = {r1 , r3 }.
id creditworthiness(cw) loan limit(ll) runtime in yrs.(rt) interest rate (ir)
1 1 30.000 5.0 3%
2 2 25.000 5.0 4%
3 3 20.000 5.0 5%
4 1 40.000 6.0 4%
5 2 35.000 6.0 5%
6 3 30.000 7.0 5.2%
7 1 40.000 5.0 3%
8 2 35.000 5.0 3.5%
9 3 30.000 5.0 5%
Table 10. Loans: creditworthiness (cw), loan limit (ll), runtime in years (rt), and interest rate (ir).
5 An Additional Example: Selection of Loans The requirements CREQ include one minimal conflict set which
is CS1 : {r3 , r4 }. Consequently, there exist two different possibili-
As a third example we introduce the domain of loans. The entries in
ties to resolve the conflict: one possibility is to change the value for
Table 10 represent different loan variants that can be chosen by cus-
the intended runtime (irt) from 6.0 years to 5.0 years and to keep the
tomers. Customers can specify their requirements on the basis of the
preferred interest rate (pir) as is. The other possibility is to change
variables depicted in Table 11. Furthermore, the different loan vari-
the preferred interest rate from 4.5% to 6% and to keep the intended
ants are characterized by their expected creditworthiness (cw), loan
runtime as is. The overall loan costs related to these two alternatives
limit (ll), runtime in yrs. (rt), and interest rate (ir). These variables
are depicted in Table 13. If the overall loan costs are a major criteria
are basic elements of the definition of the following Constraint Sat-
then repair alternative 1 would be chosen by the customer, otherwise
isfaction Problem (CSP).
– if the upper limit for periodical payments is strict – repair alterna-
variable description ri ∈ CREQ tive 2 will be chosen.
ccw current creditworthiness r1 : ccw = 3
repair alternative irt pir costs costs per year
ils intended loan sum r2 : ils = 30.000
mpp maximum periodical payment – 1 5.0 yrs. 5.0% 4.500 900.00
irt intended runtime r3 : irt = 6yrs. 2 7.0 yrs. 5.2% 6.240 891.43
pir preferred interest rate r4 : pir = 4.5%
Table 13. Loan costs for different repair alternatives.
Table 11. Overview of variables used in the example CSP definition
(loans).
• V = {ccw, ils, mpp, irt, pir, cw, ll, rt, ir} 6 Future Work
• dom(ccw) = dom(cw) = {1,2,3}; dom(ils) = dom(ll) = float;
dom(mpp) = float; dom(irt) = dom(rt) = integer; dom(pir) = A major issue for interactive applications is to guarantee reasonable
dom(ir) = integer. response times which should be below one second [3]. This goal can
• C = {c1 : ccw ≤ cw, c2 : ils ≤ ls, c3 : irt = rt, c4 : pir ≥ not be achieved with standard diagnosis approaches since they typi-
ir, c5 : see below, c6,7 : see below} cally rely on the (pre-)determination of conflict sets. Although exist-
ing divide-and-conquer based diagnosis approaches are significantly
Constraint c5 represents the entities of Table 10 in disjunctive nor- faster when determining only leading (preferred) diagnosis, i.e., not
mal form, for example, the first table row can be represented as ba- all diagnoses have to be determined, there is still a need for improv-
sic constraint {cw = 1 ∧ ll = 30.000 ∧ rt = 5.0 ∧ ir = 3%}. ing diagnosis efficiency in more complex settings. In this context,
The disjunct of all basic constraints is the disjunctive normal form. on research issue is the development of so-called anytime diagnosis
Constraints c6,7 can be used to avoid situations where the periodical algorithms that help to determine nearly optimal (e.g., in terms of
payments for a loan exceed the financial resources of the customer. prediction quality) diagnoses with less computational efforts.
Although the prediction quality of diagnoses significantly in-
costs(id) + ils creases and numerous recommendation algorithms have already been
c6 : mpp ≥ (3)
rt evaluated, there is still a need for further advancing the state-of-the-
(rt(id) + 1) art in diagnosis prediction. One research direction is to focus on
c7 : costs(id) = ils × ir(id) × (4) learning-based approaches that help to figure out which combination
2
For the purpose of our example let us assume that the customer of a set of basic diagnosis prediction methods best performs in the
has the following requirements: CREQ = {r1 : ccw = 3, r2 : considered domain. Such approaches are also denoted as ensemble-
ils = 30.000, r3 : irt = 6yrs., r4 : pir = 4.5%}. Since the based methods which focus on figuring out optimal configurations of
customer creditworthiness has been evaluated with 3, only three al- basic diagnosis prediction methods.
ternative loan variants are available (the ids 3,6,9). These variants are Efficient calculation and high predictive quality are for sure central
depicted in Table 12. issues of future research. Beyond efficiency and prediction quality,
intelligent visualization concepts for diagnoses are extremely impor-
id cw ll rt ir tant. For example, the the context of group decision scenarios where
3 3 20.000 5.0 yrs. 5% groups of users are in charge of resolving existing inconsistencies in
6 3 30.000 7.0 yrs. 5.2% the preferences between group members, visualizations have to be
9 3 30.000 5.0 yrs. 5%
identified that help to restore consistency (consensus) in the group
as soon as possible. Such visualizations could focus on visualizing
Table 12. Loans accessible for the customer with creditworthiness level 3. the mental state on individual group members as well visualizing the
individual decision behavior (e.g., egoism vs. altruism).
Since CREQ is inconsistent with the constraints in C we could 7 Conclusions
determine minimal diagnoses as indicators for possible adaptations
in the requirements. A possible criteria for personalizing diagno- In this paper we give an overview of existing approaches to deter-
sis ranking could be the costs related to a loan (see Formula 4). mine diagnoses in situations were no solution can be found. We first
provide an overview of existing related work and then focus on ba- [19] U. Junker, ‘Quickxplain: Preferred explanations and relaxations for
sic approaches to determine diagnoses in the context of two knowl- over-constrained problems’, in 19th National Conference on AI
(AAAI04), pp. 167–172, San Jose, CA, (2004).
edge representation formalisms (constraint satisfaction and conjunc-
[20] S. Leist and R. Winter, ‘Konfiguration von Versicherungsdienstleistun-
tive query based approaches). For explanation purposes we introduce gen’, Wirtschaftsinformatik, 36(1), 45–56, (1994).
three different types of financial services as working examples (basic [21] F. Lorenzi and F. Ricci, ‘Case-based recommender systems: a unifying
investment decisions, selection of investment products, and loan se- view’, Intelligent Techniques for Web Personalization, 89–113, (2005).
lection). On the basis of these examples we sketch the determination [22] A. Mackworth, ‘Consistency in Networks of Relations’, Artificial Intel-
ligence, 8(1), 99–118, (1977).
of (preferred) diagnoses. Thereafter, we provide a short discussion of [23] J. Marques-Silva, F. Heras, M. Janota, A. Previti, and A. Belov, ‘On
open research issues which includes diagnosis efficiency, prediction computing minimal correction subsets’, in IJCAI 2013, pp. 615–622,
quality, and intelligent visualization. Peking, China, (2013).
[24] C. Musto, G. Semeraro, P. Lops, M. DeGemmis, and G. Lekkas, ‘Fi-
nancial Product Recommendation through Case-based Reasoning and
REFERENCES Diversification Techniques’, pp. 1–2, Foster City, CA, USA, (2014).
[25] B. O’Sullivan, A. Papadopoulos, B. Faltings, and P. Pu, ‘Representative
[1] R. Bakker, F. Dikker, F. Tempelman, and P. Wogmim, ‘Diagnosing explanations for over-constrained problems’, in AAAI’07, pp. 323–328,
and solving over-determined constraint satisfaction problems’, in IJCAI Vancouver, Canada, (2007).
1993, pp. 276–281, Chambery, France, (1993). [26] M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer, 4
[2] R. Burke, A. Felfernig, and M. Goeker, ‘Recommender systems: An edn., 2012.
overview’, AI Magazine, 32(3), 13–18, (2011). [27] R. Reiter, ‘A theory of diagnosis from first principles’, AI Journal,
[3] S. Card, G. Robertson, and J. Mackinlay, ‘The information visual- 23(1), 57–95, (1987).
izer, an information workspace’, in Conference on Human Factors in [28] J. Tiihonen and A. Felfernig, ‘Towards Recommending Configurable
Computing Systems: Reaching Through Technology, pp. 181–186, New Offerings’, International Journal of Mass Customization, 3(4), 389–
York, NY, USA, (1991). 406, (2010).
[4] J. de Kleer, ‘Using crude probability estimates to guide diagnosis’, AI [29] D. Winterfeldt and W. Edwards, ‘Decision Analysis and Behavioral Re-
Journal, 45(3), 381–391, (1990). search’, Cambridge University Press, (1986).
[5] J. de Kleer, A. Mackworth, and R. Reiter, ‘Characterizing diagnoses
and systems’, AI Journal, 56(197–222), 57–95, (1992).
[6] A. Falkner, A. Felfernig, and A. Haag, ‘Recommendation Technologies
for Configurable Products’, AI Magazine, 32(3), 99–108, (2011).
[7] A. Fano and S. Kurth, ‘Personal Choice Point: Helping Users Visualize
What it Means to Buy a BMW’, in International Conference on In-
telligent User Interfaces IUI’03, pp. 46–52, Miami, FL, USA, (2003).
ACM, New York, USA.
[8] A. Felfernig, G. Friedrich, D. Jannach, and M. Stumptner,
‘Consistency-based diagnosis of configuration knowledge bases’, Ar-
tificial Intelligence, 152(2), 213–234, (2004).
[9] A. Felfernig, L. Hotz, C. Bagley, and J. Tiihonen, Knowledge-based
Configuration – From Research to Business Cases, Elsevier, Morgan
Kaufmann, 2014.
[10] A. Felfernig, K. Isak, K. Szabo, and P. Zachar, ‘The VITA Finan-
cial Services Sales Support Environment’, pp. 1692–1699, Vancouver,
Canada, (2007).
[11] A. Felfernig and A. Kiener, ‘Knowledge-based Interactive Selling of
Financial Services with FSAdvisor’, in 17th Innovative Applications of
Artificial Intelligence Conference (IAAI05), pp. 1475–1482, Pittsburgh,
Pennsylvania, (2005).
[12] A. Felfernig, J. Mehlau, A. Wimmer, C. Russ, and M. Zanker,
‘Konzepte zur flexiblen Konfiguration von Finanzdienstleistungen’,
Banking and Information Technology, 5(1), 5–19, (2004).
[13] A. Felfernig, M. Schubert, G. Friedrich, M. Mandl, M. Mairitsch, and
E. Teppan, ‘Plausible repairs for inconsistent requirements’, in 21st In-
ternational Joint Conference on Artificial Intelligence (IJCAI’09), pp.
791–796, Pasadena, CA, (2009).
[14] A. Felfernig, M. Schubert, and S. Reiterer, ‘Personalized diagnosis for
over-constrained problems’, in 23rd International Conference on Arti-
ficial Intelligence (IJCAI 2013), pp. 1990–1996, Peking, China.
[15] A. Felfernig, M. Schubert, and C. Zehentner, ‘An Efficient Diagnosis
Algorithm for Inconsistent Constraint Sets’, Artificial Intelligence for
Engineering Design, Analysis, and Manufacturing (AIEDAM), 25(2),
175–184, (2012).
[16] E. Freuder, ‘In pursuit of the holy grail’, Constraints, 2(1), 57–61,
(1997).
[17] G. Friedrich, ‘Interactive Debugging of Knowledge Bases’, in
DX’2014, pp. 1–4, Graz, Austria, (2014).
[18] D. Jannach, M. Zanker, A. Felfernig, and G. Friedrich, Recommender
Systems, Cambridge University Press, 2010.