Chatbots as conversational recommender have gained increasing importance over the years. The chatbot market offers a variety of applications for research and industry alike. In this paper, we discuss an implementation that supports the use of our recommendation algorithm during chatbot communication. The program eases communication and improves the underlying recommendation flow. In particular, the implementation makes use of our model-based reasoning approach for improving user experience during a chat, i.e., in cases where user configurations cause inconsistencies. The approach deals with such issues by removing inconsistencies in order to generate a valid recommendation. In addition to the underlying definitions, we demonstrate our implementation along use cases from the tourism domain.
Recommender systems aim to lead users in a helpful and individualized way to interesting or useful items drawn from a large space of possible options. Recommender systems may utilize knowledgebases for guiding the users through the whole process of finding the right recommendation, i.e., a recommendation that satisfies the user’s requirements, needs, or expectations. Most recently, conversational agents like chatbots have gained importance because of the fact that they – in principle – offer a well-known and ideally more intuitive interface for human users, i.e., either textual or speech interaction.
In previous work [
This paper is a direct successor of our previous work, where we report on an implementation of our chatbot approach. In particular, we discuss the implementation details, present experiences gained, and finally introduce the results of an evaluation of the implementation. The evaluation is based on a case study from the tourism domain, i.e., a scenario where a user wants to book a hotel in a certain city. The obtained results show that the proposed chatbot approach is applicable and beneficial for the intended purpose. Furthermore, we gained experiences about the limitations of the approach. For example, it seems that entropy is not always the best measure for selecting questions to be answered, and further research is needed.
The main contributions of this paper can be summarized as the follows: 1. An implementation of an algorithm that is based on model-based diagnosis and Shannon’s information entropy to solve recommendation problems and 2. the evaluation of the system with synthetic and real-world data sets.
The remainder of this paper is organized as follows: In the next section we give an overview of our algorithmic approach. Afterwards, we present the implementation of the algorithms and show evaluation results in greater detail. Finally, we discuss related research and conclude the paper. 2
In our previous work [
The inconsistent requirements problem requires information on the item catalog (i.e., the knowledge-base of the recommendation system) and the current customer’s requirements. Note that the knowledge-base of the recommender may be consistent with the customer’s requirements (i.e., the customer’s query) and an appropriate number of recommendations can be offered. In this case, the recommendation system shows the recommendations to the customer and no further algorithms have to be applied. Otherwise, if no solutions to the recommendation problem are available, then the minimal set of requirements, which determined the inconsistency with the knowledge base, have to be identified and consequently offered to the user as explanation for not finding any recommendation. The user can in this case adapt the requirement(s) (relax it/them). Here we borrow the idea from MBD and introduce abnormal modes for the given requirements, i.e., we use Ab predicates stating whether a requirement i is should be assumed valid (:Abi) or not (Abi) in a particular context.
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). The Ab values for the requirements are set by the model-based diagnosis algorithm so that the assumptions together with the requirements and the knowledge-base are consistent. In the following, we define the inconsistent requirements problem and its solutions.
More formally, we stating the inconsistent requirements problem as follows: Definition 1 (Inconsistent Requirements Problem). Given a tuple (KB; REQ) where KB denotes the knowledge base of the recommender system, i.e., the item catalog, and REQ denotes the customer requirements. The Inconsistent Requirements Problem arises when KB together with REQ is inconsistent. In this case we are interested in identifying those requirements that are responsible for the inconsistency.
A solution or explanation to the inconsistent requirements
problem can be easily formalized using the analogy with the definition of
diagnosis from Reiter [
A set of inconsistent requirements is minimal iff no other set of inconsistent requirements 0 exists. A set of inconsistent requirements is minimal with respect to cardinality iff no other set of inconsistent requirements 0 with j 0j < j j exists. From here on we assume minimal cardinality sets when using the term minimal sets.
The second problem occurring during a recommendation session is the availability of too large number of recommendations, which have to be narrowed down to a reasonable number. The too many recommendation problem can be solved again using ideas borrowed from model-based diagnosis. In diagnosis, we have the similar problem of coming up with too many diagnoses because of too less observations known. The corresponding problem in case of recommendation is that we do have far too less requirements from the user.
Hence, we have to ask the user about adding more information in
order to reduce the number of available solutions. In model-based
diagnosis Shannon’s information entropy [
Algorithm 1 provides recommendations in the context of chatbots making use of diagnosis and Shannon’s information entropy computation. EntRecom converts the available knowledge into a corresponding constraint model and checks its consistency. If the knowledge is inconsistent, the algorithm tries to find a requirements that can be retracted by the user in order to get rid of the inconsistency.
Afterwards, EntRecom searches for the best requirement to be set by the user in order to reduce the number of solutions if necessary. The algorithm stops when reaching a set of recommendations that has a cardinality of less than n.
With the provide algorithms a chatbot for recommendations can be build that is able to deal with inconsistent requirements as well as missing requirements in a more or less straightforward way making use of previously invented algorithms.
Algorithm 1 EntRecom(KBD; REQ; n) Input: A modified knowledge base KBD, a set of customer requirements REQ and the maximum number of recommendations n Output: All recommendations S 1: Generate the constraint model CM from KBD and REQ 2: Call CSolver(CM ) to check consistency and store the result
in S 3: if S = ; then 4: Call MI REQ(CM; jREQj) and store the inconsistent re
quirements in IncReqs 5: Call askUser(IncReqs) and store the answer in
AdaptedReqs 6: CM = KB [ (REQ n IncReqs [ AdaptedReqs) 7: go to Step 2 8: end if 9: while jSj > n do 10: Call GetBestEntrAttr(AS ) and store the result in a 11: AS = AS n a 12: Call askUser(a) and store the answer in va 13: S = R (S; va)) 14: end while 15: return S 3
For the user, the interaction with the recommender system within the chatbot starts, when he or she formulates a query for a search within the domain. The natural language processing framework Rasa2 parses this query and passes it on to the EntRecom-algorithm. The recommender algorithm then searches a previously conducted and preprocessed knowledge base. Depending on the satisfiability of the generated constraint model, results are presented to the user. If necessary the user is asked follow up questions regarding his or her requirements until we have results to return to the user.
When the query can be answered, EntRecom exits and the user can continue interacting with the Rasa-based chatbot.
As mentioned before, we choose a tourism domain, searching for a hotel to be more specific. The process of searching a hotel in an iterative conversation helps us to see the capabilities and shortcomings of the algorithm.
For our tests, we chose the community-curated data from Open Street Maps (OSM). We use the python bindings for Microsofts’ Z3 framework as a constraint solver. For language processing and basic interaction with the user, we utilize the Rasa framework. Rasa is used for natural language understanding by extrating the users’ intend and requirements but can also respond immediatly with an answer (without calling EntRecom) when it detects the users’ intend to chitchat.
In a first step, we query the OSM-API for hotels in a predefined region. The size of the region is a major factor for performance. Because of this, it is reasonable to let the user select a region on initialization.
To conduct our internal knowledge base, we process the exported data set in the following way: As some attributes do not add humanreadable information or tend to mislead users, we have to filter them out. This is especially necessary because some classes of attributes have a severe impact on later steps in our recommender system. For example, categories like ”fixme” (annotation from an OSM user) would give the user no advantage in a real-world scenario and in this case, would lead to unwanted recommendations. We use a whitelistfilter for the attributes of every entry in the data set. Furthermore, not every entry in the OSM data has the same fields, why we maintain a list of all attributes in a data set. If an entry does not include a certain attribute, we add it with a value of False. This leaves us with a ”normalized” data set.
After our preprocessing step, every entry in the dictionary has the same number of attributes we add uniform clauses to our constraint model. An exemplary normalized clause looks like this: (amenity = "none" ^ addr : city = "Graz" ^ name = "P arkhotelGraz" ^ cuisine = "none" ^ : : : ^ smoking = "isolated" ^ wheelchair = "limited" ^ swimming pool = "none" ^ stars = "4" ^ tourism = "hotel"). Regarding data types, we choose between two different approaches, when creating the Z3 constraint model. The first one being data type selection for every attribute in the domain and the second one being string translation for every value, regardless of the specific class of an attribute. In our implementation, every attribute and value is translated to a Z3 string. While this may result in slower runtimes, we ensure flexibility, as data types may vary across attributes. Usually, the user is asked to select a region of interest. For our tests, we use a data set of a specific size. This is a very critical and, depending of the size of the test set, time consuming step. Therefore, we try to do it only once when the user initially specifies an area. This Z3 constraint model, consisting of OR-connected uniform clauses of Z3 strings is our main knwoledge base within EntRecom and shall be refered to as kb and subsets therof as S in the remainder of this paper.
The first interaction the user has with our chatbot implementation is handled via the trained natural language understanding (NLU) model within Rasa. If the user’s intent to search within the domain ”hotels”, our recommender is called via a webhook, and the parameters are passed over. This call to our internal API is the only interaction between EntRecom and the chatbot framework, Rasa, in our case, which leads to very low coupling and a high degree of flexibility. The parameters represent the NLUs interpretation of the users’ query and give us our initial set of requirements. 3.2
In this section, we are describing the implementation of the previously introduced algorithm EntRecom.
Before the algorithm ready to use, we have to prepare our data set, generate the constraint model and interpret the user’s intent. Then we enter the EntRecom-implementation. As described before, if the query is satisfiable for our knowledge base and the given maximum number of results, we return our recommendations and exit EntRecom.A maximum of n hotels is presented to the user, we retrieved from the knowledge base, with n representing a preselected maximum number of results.
Though, as stated in [
We could get no results at all. In this scenario, we call the function M iREQ. 3.2.1
This part of the algorithm is called, when the query is satisfiable, but
the result does not lie within [n]. Therefore, we have to add further
constraints to our model. Because we want to occupy as little of the
user’s time as possible, we have to efficiently select additional
constraints. This is done by choosing a category out of the domain which
best splits the current subset S of the data set. The criterion for our
selection is Shannon’s information entropy [
H(X) =
X P (xi)log(P (xi))
i
To apply entropy as a measure, we have to restructure the data slightly. AS represents this restructured version of S, which maps every attribute in the domain to all values of its occurrences in S. This is realized with python dictionaries of the form: "attribute1" : ["value1"; "value2"]; "attribute2" : ["value1"]; :::. After computing the number of occurrences of every value for a (a) SAT (b) MiREQ specific attribute, we now calculate the entropy, for every attribute. The attribute with the highest entropy splits the data set S most effectively. As mentioned above, some attributes may lead to unwanted recommendations. One reason for this is the appearance of seemingly random values when looked at them lacking context. This could be attributes internally used within OSM, for instance. Fields like ”source” often have seemingly random values like ”survey” or ”Kleine Zeitung”. The same pseudo-randomness can be observed with attributes like ”housenumber” which can take an arbitrary integer value. Those values appear in many data points and, when observed isolated, do not contribute any information with regard to splitting the data set. When computing the information entropy based on attributes lacking spatial ordering or clustering properties, we are not dividing the data set strategically but randomly. This is why we chose to exclude them from our knowledge base beforehand. If several attributes occur with equal entropies in the data set, we can randomly select one of these categories, as all of them split the data equally well. In the last step, the user is asked for selecting one value for this category. The user’s selection is added to the set of requirements and EntRecom gets called again. 3.2.2
This part of the algorithm is called, when the query is not satisfiable
for our knowledge base KB with the user-defined set of
requirements REQ. Following [
We developed our tests concentrating on the algorithm itself and the
data structures needed for execution. The data preprocessing was not
in the focus of this test. For our tests with synthetic test data this is
especially true, as they use a adapted version of EntRecom without
user interaction, as depicted in Figure 5. The goal of our experiments
is to show potentials for optimizations of the implementation, as well
as proofing the versatility of the algorithm proposed in [
In our tests, we used both, synthetic and real-world data. For benchmarking and basic experiments, we mainly used synthesized data, while real-world data, specifically from Open Street Maps is h) Ranges (e.g. distance-to-the-center, price-category) ad a) Boolean values appear often in real-world data and are easy to process. This class represents attributes like internet-access or payment-credit-card in the domain tourism and esp or abs in the automotive domain. ad b) Arbitrary integer values appear often as counter variables like vis
itors, likes or 5-star-reviews ad c) Floating-point numbers occur within both domains, tourism, and
cars in various forms. This class covers all attributes in the context Figure 5: Focus of Tests with Synthetic Data of distance, like distance-to-the-center for a hotel or mileage for a car. It also stands for location attributes given in coordinates important to ensure the flexibility and robustness of the implementa- (longitude, latitude) and mean values like user-rating. tion in real-world scenarios. ad d) Strings are very versatile and therefore used in many ways in different sources. In many cases, strings contain informational value 3.3.1 Real-World Test Data beyond what a number may cover. But often strings are used in places, where the informative content is not higher than numberAs described before, we use data from Open Street Maps for our valued attributes and could be represented with Boolean values or tests. First, we want to observe, how the algorithm copes on real- numbers instead. This is true for several classes of attributes like world data and which degree of data preprocessing and filtering of stars with values of ”4-star”. the data is necessary. Furthermore, we developed the rules for gener- ad e) The name attribute is always a string and does not have to but is ating our synthetic test data based on the exported data from OSM. likely to include a domain-specific term in its value. For hotels,
For this part of our evaluation, we empirically tested the algorithm this would be ”Hotel” or a synonym thereof. Because of these refor usable results as well as automated tests for exhaustive testing on curring terms and the omnipresence over all domain-specific data the data. sources, we treat this attribute separately from the more general string class. When generating data sets, we introduce these terms 3.3.2 Synthetic Test Data into our samples regularly.
ad f) Fields like city or manufacturer contain frequently reappearing Our modus operandi for generating and conducting tests with syn- values, which makes it special regarding information entropy and thetic data can be described as follows: therefore interesting to us.
ad g) Stars of a hotel can be represented with 1 to 5, which makes a 1.) Definition of attribute classes and generation of data sets reappearance in this category very probable. 2.) Definition of requirement sets and classifying them within a test- ad h) As we want to simplify the selection process, we reduce the date ing matrix to the year. This results in an integer value often constrained by an 3.) Performing speed tests following the testing matrix upper boundary being the current year and a case dependent lower
To evaluate our results for the performance test, we order tests boundary. Depending on the specific attribute, these values may within a three-dimensional testing matrix. The first axis of this ma- recur frequently. trix represents the size of the test set. The second axis represents the ad i) Ranges are special because they consist not only of one, but two number of attributes and the last axis represents the number of al- boundary values. For simplification reasons, we categorize ranges lowed results n. The value at every position in the matrix represents within the relative classes: low, med and high. Of course, these the called subfunction within our recommender algorithm. range classes are also very likely to reoccur.
We randomly generated data sets of different sizes and with different numbers of attributes for our performance tests. Because data Our synthetic data is randomly generated with respect to those within the domains ”hotels” and ”cars”, have several distinct proper- classes of attributes and with varying occurrences of the different ties, we set up our test data following certain rules. To achieve this, types. we categorized the attributes dependent on the data type of their corresponding values. Furthermore, we added complementary classes 3.4 Results based on certain characteristics of the domain.
This results in the following basic classes of attributes based on their data type:
The results are splited in two parts. First, we discuss the results of the synthetic data, followed by the proof of concept results with realworld data.
Using the synthetic data, we define sets of requirements to test the algorithm on. These sets belong to one of the following classes relative to the knowledge base e.g. the test data and the given n, they are tested with: i) Satisfiable with n or less results. This leads to a direct return from the EntRecom-algorithm, presenting us the results S the constraint solver found. ii) Satisfiable with more than n results. In this case, we have to call GetBestEntrAttr, which calculates entropies for all attributes. Another interaction with the algorithm is needed, as we have to select a value for the attribute with the highest informational content. iii) Not satisfiable. In this case, we have to call M iREQ which iteratively chooses subsets of REQ until it finds the largest satisfiable subset. Its complement is the set of inconsistent requirements s. Again, another interaction through AskU ser is necessary. Now we have to select a requirement out of s we want to keep in REQ the other constraints are dropped.
To classify the requirement sets for every test set according to the three classes from above, we use an adapted version of EntRecom, which does not return results or perform any recursive calls. The purpose of this classification is, to be able to identify test results with regard to the sub-functions called within EntRecom. The class of REQ - either i, ii, or iii - for a certain test configuration represents the value of the three-dimensional testing matrix.
After classification, we perform our tests on the generated data. A typical test-scenario starts with the users first interaction with the chatbot environment, which, in turn, results in setting up the knowledge base. Regularly the user is asked to select a region of interest. For our tests, we use a data set of a specific size. Then a set of requirements and a maximum for the expected results are chosen. We now perform a test for every class in the testing matrix and get results in the form of execution times.
For a fixed n of 5 and tests performed with one to five requirements in the sets, we plot the function calls of M iREQ and GetBestEntrAttr on increasingly sized test sets. In case, we obtain a result for our query which lies within n, our constraint solver CSolver is the only function call made.
As you see, the function calls of M iREQ decrease, while the calls of GetBestEntrAttr increase for larger test sets. While this basic assumption holds for real data, the impact is not as drastic, as users tend to perform queries with less than five requirements initially.
The algorithm was also used with real-world data. Therefore, we inserted the data from OSM into the knowledge base. We interact with the textual chat-like web interface in the intended way and get the correct results from the algorithm. The algorithm returned a result set within a few iterations and these results fit to the user specification.
These experiments show also that there is a problem of relevance of attributes. The attributes, which have a high entropy to reduce the result set, are not nessesarily relevant for users. Our tests show that i.e. the attribute wheelchair, which is part of accessibility, has a high entropy but will not be interesting for a large amount of users. This issue has to be addressed in an upcoming version of the algorithm.
The application of model-based reasoning, and especially
modelbased diagnosis, in the field of recommender systems is not novel.
For example, papers like [
Papers that deal with the integration of diagnosis and constraint
solving are [
Human-chatbot communication represents a broad domain. It
covers technical aspects as well as psychological and human
perspectives. Contributions like [
Sun et al. [
Papers like [
The topic of recommender systems with conversational interfaces
is shown in [
In this paper, we showed an implementation and its evaluation of EntRecomm, an algorithm using model-based diagnosis and Shanon’s information entropy. In our tests, we used both, synthetic and realworld data. For benchmarking and basic experiments, we mainly used synthesized data, while real-world data, specifically from Open Street Maps is important to ensure the flexibility and robustness of the implementation in real-world scenarios. We also showed the performance for different data sets and also revealed open issues, like the relevance of chosen attributes, which is already a starting point for future work. Another important step will be a user study to evalute the acceptance of the algorithm.
Research presented in this paper was carried out as part of the ASIT-IC project that is co-financed by the Cooperation Programme Interreg V-A Slovenia-Austria 2014-2020, European Union, European Regional Development Fund.