Information retrieval (IR) chatbot is a special class of virtual assistants, which is widely used nowadays in customer support services. However, the work of modern IR retrieval systems is limited by simple queries to the database, which does not utilize all the potential of interaction with the user. In this paper we implement an FCA-based approach to deliver the relevant information the user has requested. A developing approach integrates a concept-based model build upon the database and intelligent traversal through it. The proposed algorithm has been implemented as an additional function within the existing IR chatbot. In this paper we also enlighten the perspectives for further development of the proposed system. Formal Concept Analysis (FCA) technique and Pattern Structures as its extension are proposed to process unstructured data (objects with a text description), which has become a common way of presenting various items recently.
This paper considers the main principles which underlie information retrieval (IR)-chatbots [
It should be mentioned that in most cases traditional IR-chatbots send queries to the database ignoring any knowledge models that could be built upon the database. The motivation of the proposed approach is that instead of simple queries to the database, we build a knowledge model and traverse it with the proposed two-level interactive algorithm. Interactive part allows the chatbot to adjusts to the user’s preferences automatically. In this paper we aim to explain the main principles the proposed algorithms are based on and to present the experimental results obtained for real data. We also discuss the future direction of this research.
The paper is organized as follows. In Sect. 2 we present the basic notions of FCA and PS. Sect. 3 starts with a small example where IR-chatbots might be used, and then we introduce a knowledge model that is the basis for IR-chatbots. In Sect. 4 we discuss principles for the IR-chatbot functioning. In Sect. 5 we present the experimental results. We conclude and give the direction for future work in Sect. 6 and 7.
The main theory that lies upon the proposed methods is Formal Concept Analysis (FCA) and Pattern Structures (PS). Let us introduce some basic notions of the theory.
is a set of objects,
= { 1,
2, ..., } is a set of attributes, and ⊆
×
In Formal Concept Analysis theory [
is called the (formal) extent, and is called the (formal) intent of the concept (, ). A partial order ≤ is defined on the set of concepts as follows: (, (, ) is a subconcept of (, ), while (, ) a superconcept of (, ) . ) ≤ (, ) if ⊆ ( ⊆ ), a pair
As the standard definition of FCA is related to data presented in binary format, which does
not always suit the real data, the Pattern Structures were introduced [
A Pattern Structure is a triple (, (, ⊓ ) , ), where is a set of objects, is a set of all possible object descriptions, and (, ⊓ ) is a meet-semilattice of object descriptions. Mapping ∶ → takes an object to its description ∈ (, ⊓ ). Galois connection between (2 , ⊆) and (, ⊑ ) is defined as □ = ⊓ ∈ ( ) , ⊆ , □ = { ∈ | ⊑ ( )} for ∈ (, ⊓ ), where ⊑ ( ) ⇔ ⊓ ( ) = . A pair (, ) for which □ = and □ = is called a pattern concept.
Stability indices for formal concepts were introduced in [9], [10] and modified in [11]. Intentional stability of concept (A,B) is the probability that B will remain closed when removing a subset of objects from extent A with equal probability ((, )) ∶ { | ⊆ ∣ ′ = 2| | } | .
( ∗, ∗)≤(, )| | − | ∗|.
The concepts with the high values of ((, )) are more stable regarding random removal of
the objects. The computing stability is # -complete. In practice, one uses its approximations
[12], [
In the beginning, we would like to consider a small use case where the described approach of building knowledge domain and its traversal can be implemented. Table 1 presents the database that is used in this example. This database is a small fragment of the database used in experiments (Section 5) with a shortened number of objects and attributes describing them.
Brand
Battery
Weight
Camera
RAM
Screen Size
8 Silver, Gray, Pink, Gold
Silver, Gold Silver, Gray
Gray Gray Silver
Price
The objects { 1, 2, 3} are tablets, they belong to the same category “Tablet”, the objects { 4, 5} are laptops, they belong to the category “Laptops”, while 5 also belongs to “Transformerlaptop” category, 6 is a laptop and also an ultrabook, so, it also belongs to two categories.
The scenario of IR-chatbot performance is the following, the user aims to find some items, and the chatbot provides some features that the user may refine to filter the items. As has been mentioned in the introduction, the user may know some attributes he expects to get within the item at the beginning of the search, or he may not. In the latter, the only information he possesses is that he wants to purchase some object that satisfies his requirements, which are not formulated yet.
The standard IR engine usually proposes a set of attributes that the user should refine. The attributes can be chosen in diferent ways, we have distinguished some of them: — show only the most general attributes for refinement, i.e., price, brand, average customer review, etc. (such kind of refinement might be irrelevant for users); — show the most frequently refined attributes (it does not take into account how diverse the range of goods within a specific category is and is not adapted to specific preferences of a user); — show all attributes (this approach is rarely used in practice since it ofers a wide range of options to specify and worsens the user experience).
After the features are revealed the user filters some of them, and the chatbot sends the query to the database. In the end, the user gets a huge list of objects with the set of all possible characteristics, and he/she should be able to find one (or several items) that meets all his/her requirements. This approach has an obvious drawback, a web search engine may propose irrelevant attributes to refine or does not take into account the user preference adjusted depending on the availability of goods.
The example above demonstrates the main problem of the existing tools: in case of very general queries the search engine does not provide user-friendly interface for attribute refinement, i.e., it does not provide convenient tools to discover a variety of objects the user might be interested in.
As we have mentioned above this work is a logical continuation of the work [
It should be mentioned that IR-chatbots usually work with huge databases containing extremely heterogeneous items. These objects (goods) are described by completely diferent attributes. Even in our running example, the goods from category “Tablet” and “Laptop” have diferent nonoverlapping features ( “Camera” for tablets, and “GPU” for laptops). If we consider more complex databases, then we can see various goods that have nothing in common. Thus, it is reasonable to use this information in the process of building a knowledge model.
A two-level knowledge model suits this problem. On the upper level the objects are divided into several very general categories, which do not overlap and using FCA theory, we build the upper-level model where the set of objects contains the initial objects from the dataset and the attributes are binary, defining whether the object possesses the following characteristic, or not. The example of such kind of general categories is electronic devices furniture, clothes, building materials, etc. Thus, on the upper level of knowledge model, the groups of the most similar objects (in sense of having a specific characteristic) are revealed. Then, on the bottom level, we process the objects belonging to the same group (concept) more accurately, considering the specific value of each attribute.
The heterogeneous objects are the ones described by diferent attributes that are never used together. At the upper-level model they are put into diferent categories, e.g., consider data from 1, the tablets have the unique attribute “Camera”, which other goods do not possess, so the category “Tablet” is general enough for the upper level. At the same time, all notebooks have an attribute “GPU”, which separates them from the objects belonging to other categories; thereafter, “Laptop” could be the upper-level category for these goods as well.
Let
be a set of objects, described by a set of attributes , where every particular domain of values ( ). We denote the set of all possible values by , i.e., ∈ has a
( ) ∣ and attributes . Thus, ′ ⊆ ∈ . Every object is described by a small subset of attributes from . For objects we define a binary relation as follows, ( ) = 1 ⇔ is defined for is a subset of attributes that is used to describe object , and ′ ⊆ a subset of attributes that are used to describe every object in . The “is defined ” relation for objects from Table 1 is given in Figure 1 (a). The degree of objects homogeneity ⊆
∈ |/| |, is the rate of their common attributes. A sublattice of concepts with the homogeneity rate ℎ( ) ∈ [ℎ1, ℎ2] represents the coarse categorization model. The lower bound ℎ1 prevents from creating too general categories, while the upper bound ℎ2 allows not considering very homogeneous objects at the upper level. For example, if we get a concept with the intent which contains only one feature out of 20 initial, then its homogeneity rate = is query refinement procedure for this group of objects, as they are extremely varied. ℎ( ) is 0.05, this means that this group of objects is too general. So, it is useless to launch the
The upper level of the knowledge model is a fragment of a concept lattice , computed on the “is defined ” relation where the concepts meet the homogeneity rate requirement and augmented with the set of category names. Figure 1 shows the table represented “is defined ” relation for the objects from Table 1 (a), and for that data (b).
Homogeneous objects, which are the groups of objects scribed by the high rate of similar attributes. To compute refined groups ⊆ , where (, ) ∈ , are dewe took the attributes that defined for all the objects in and build a pattern structure on the corresponding ⊆ data fragment. The derivation operator (.)□ and intersection operator ⊓ are defined diferently for diferent attribute types and may also depend on the semantic behind an attribute. For example, the real-valued features 1 and 2 can be presented as the ranges [ 1, 1] and [ 2, 2]; the intersection operator ⊓ is defined as follows, 1 ⊓ 2 = [ 1, 1] ⊓ [ 2, 2] = [ ( 1, 2), ( 1, 2)]. Thus, we get refined groups of objects within each pattern structure and denote these groups by ( ). This pattern structure is the basis for further interaction with the user and the refinement of his query.
The basic idea of query refinement was introduced in [
The two-level knowledge model described above is used by chatbots to improve user search experience in case of imprecise queries. The proposed approach supposes the interactive manner of query refinement during the traversing of the bottom level model. As the result, the chatbot working by the proposed scheme is flexible in terms of considering both user preferences and the available set of objects with consequently specified features.
The interactive query refinement consists of two main steps: 1. Navigating to the group of homogeneous objects, i.e. a formal concept (, ) ∈ at the upper level. 2. Query refinement within a group of homogeneous objects by walking through pattern concepts in ( ) at the bottom level.
Let us consider the second stage of the proposed algorithm, because several slight modifications
have been included there in comparison to the previous version [
The set of homogeneous objects and the feature that describe it are directed into the bottom level of knowledge model in the form of formal concept (, ) ∈ . The algorithm working at this level calculates the corresponding pattern structure ( ) and continues the process of query elaboration.
The algorithm starts working with a pattern structure ( ) and, optionally, values of some attributes from M. The basic idea of the algorithm is to walk through pattern structure jumping from one promising concept to another, interacting with the user simultaneously and updating the user request. After an iteration the chatbot specifies the concept he proposes to the user, thereafter, the user gets the most specific concept, containing one or several elements from the database. The user might be satisfied with the result, then the goal of interaction is achieved, or not (if the remained goods contain features which are also not suitable for the user). If the final result is negative, then the chatbot can start another session and try to find suitable goods, starting from another promising concept.
The chatbot starts its work from the most general concept or the most specific concept that satisfies user initial request (considering values of some attributes from ), i.e. ( , ). The most promising concepts are the lower neighbors of ( , ). These neighbors are ranked w.r.t. Δ-measure and the number of lower neighbors. Both of these characteristics are referred to the concept stability. Then starting with the most “stable”, in accordance with Δ-measure, concept the algorithm uses isVaried function to reveal the attributes that have the most diverse value inside the concept. Then these attributes are ofered to the user for refinement.
Thus, the chatbot does not propose to the user the whole range of values (⋅). This speciifcation facilitates the decision-making process. The specified values are used to find the most general concept ( , ) where all objects have values . Its lower neighbors are possible groups of more specific concepts. We sort them by Δ-measure and the number of lower neighbors. Then a new iteration of the query refinement is launched.
Algorithm 1: Query refinement
Data: ( ), , Result: , if the used have found the item( ) he searched for,
← ; ← ∅ // set of relevant objects; , ) ← ℎ (( ), ); ←
( ℎ ( , )) // first concepts proposed for refinement; ← ∅ // attributes marked by user as irrelevant; while ≠ ∅ do ( , ) ← ( ); ← ; ∗ = ∣ ∈ ⧵ , ∈ otherwise ( , ) // the set of attributes for possible refinement; if ∗ ≠ ∅ then ∗ = ( ∗); ← ∗ // the attributes the user does not want to refine; ← { ∣ ∈ ( ), ∈ ∗ }; // ask the user, if he is already satisfied with the results, he type εyesε, and run, W ( ); ← ← ℎ if ≠ ∅ then ( , ) ← ℎ ← end end ( ℎ ( , ), ); ( , )); end return
As the possible improvement for the algorithm we consider including the additional measure for ranking the concepts. In the current version of the algorithm the concepts are ranked only by Δ-measure, which defines stability. However we can also include some statistical measures about the attributes, for instance, if the most frequently refined attributes are varied inside the concept, then it may have greater weight than other concepts because in general users are interested in this specific attribute. Another variant is to apply the machine learning technique of informative feature selection into this step. For example, if we have some rate given by the users about the product we can calculate which features are the most essential for determining the high grade of the object, thereafter the concepts with varied informative features can be ranked higher in comparison to the others. Let us illustrate the principles of query refinement using the running example. Having built a patter structure for a set of homogeneous objects we got the most general concept with extent { 1, 3}, { 2, 3}, and { 1, 2}. The obtained concepts are similar to each other in comparison of Δ-measure and the number of lower neighbors, so the chatbot can start refinement with any concept. For the extent 1, 3 the most varied attributes were real-valued characteristics which are the “battery” and “screen size”. The user did not want to continue refinement because the proposed range of screen sizes did not meet his expectations, the user understood that he wanted the screen size to be smaller than 10.5. The next attempt was successful, and the user managed to find the relevant attribute after the one iteration. Figure 2 illustrates the refining process for the described case.
This running example does not show the advantages of using the proposed method, because the number of objects is extremely small, however, it illustrates the principles of the work.
The experiments were performed using the real data provided by online stores available on the Internet. The names of brands and other confidential information were replaced by some universal names, like “Brand 1”, “Brand 2”, etc.
The data is presented in the form of the dataset containing information on various types of PCs, such as laptops, ultrabooks, tablets, and smartphones, 200 objects in general. Each of them is described by various attributes, the 16 main characteristics are overviewed. However, as it already has been mentioned, the items belonging to diferent categories possess diferent attributes. Thus, the first part of the proposed methods allows us to identify the group of objects sharing similar attributes and work with them separately. The observed characteristics are the follows: Brand, Battery, Camera resolution, Weight, Warranty, Ports, Processor, OS, RAM, GPU, CPU, Size, 4G LTE, Sensor, Color, and Price.
The experiments were held as follows, the users were given several scenarios of interaction with the chatbot including the initial request and the set of relevant and irrelevant attributes. The scenarios were generated randomly, the object desired by the user may be in a dataset, then the expected outcome is the list of objects that satisfies users’ request, or the user might want the object that is not contained in the database, then the final step of the interaction is the empty list, and the previous step provides the user with the objects which are the closest to the desired one.
The possible scenarios are presented in Figure 3.
Table 2 presents the results of the experiment. During the experiments we have evaluated the number of correct outcomes when the required item was in the database (“Satisfaction with the result (positive)” column), and the number of correct outcomes when the required item was not in the initial database (“Satisfaction with the result (negative)” column). This metric measures how many times the chatbot has found the relevant items, if they are in the initial database, or has revealed that the desired item cannot be found when it is true in reality. Secondly, we calculate the average number of iterations required by the chatbot to obtain the ifnal result for the user ( “The average number of iteration till the final result” column). This characteristic shows how many times the user needs to refine his query in order to obtain a satisfactory result.
As we saw in the previous section the number of iterations can depend on the choice of the initial concept that we choose in accordance with Δ-measure. So, we calculate the total number of iteration within all the attempts of the chatbot and normalize it by the total number of the performed scenarios, which is 60.
Thus, experimental results show that the proposed architecture works successfully. In one case only the chatbot could not find the item that meets user’s requirements fully. The mistake was obtained in the scenario when the user requested the tablet with the screen size more than 13. The chatbot found 10 items with the screen size from 17 to 21 inches and stopped the interaction process, while the user wanted to specify this characteristic more and choose only the tablets, which screen size is 17. This mistake was obtained due to the specificity of isVaried function. The other cases were performed without any mistakes.
Some peculiarities were revealed when the chatbot processed the “negative” scenarios, where the desired item could not be found in the database. For example, if the user asked for a tablet, cheaper than 800, with the battery more than 8000, and lighter than 0.4 and the user inserted these requirements sequentially, step by step, then the chatbot in three iterations revealed that the desired item cannot be found in the database, however, it also found the list of two items with slightly larger weight (0.456, 0.483). So, in this case the chatbot also provided the list of the items which had similar characteristics to the desired one. In the case when all three limits on the features were written simultaneously, the chatbot just said that it was not able to find the requested element, and the list of the closest items was not proposed.
The average number of iterations the chatbot performs is 4.7, which is a satisfactory result.
Finally, we would like to discuss the ideas about the further direction of the research. In future work we are planning to process unstructured data or descriptions written in natural language. It is a known fact that besides some structured information, contained in the database, the objects can also be described by various data presented in the text form, which is also a great source of information. This could be the users’ feedback on the product or just a general description that the object has. The search based on this data can be helpful when the user is trying to find some items, but he also desires to know what advantages and disadvantages were revealed by the users of this item in real life.
There the proposed technique without modifications cannot be applied, because we do not have a clear structure (like features and their values) for each item. The FCA has been developed as the tool for working with the text data using Pattern structures and so called parse thickets. Using some NLP techniques we are able to create the features from the texts, so called informative parts of the texts, and then use some similarity measure to unite the items in the one concept. For instance, let us consider the phrases “this model has weak battery”, “the work without charging is so little”, “The autonomous work is frustrating”. All of these phrases represent the common feature of several models of the laptop which is a bad battery, however, all of them have several diferent forms, but we need to reveal their similarity This can be done by using some widely spread embedding vectors to detect whether the phrase has something in common, or not. The other problem is to detect Δ-measure for this kind of data, w.r.t., how we can measure the stability of concept with a text description. Thus, our future research will be dedicated to the generalization of the proposed model to the task of processing the unstructured data.
In this paper, we discovered a model of the IR-chatbot based on two-stage query refinement using FCA theory and Pattern Structures. We overviewed the basic principles of its work and presented the experimental results obtained with the real data.
The experiments showed that the chatbot is efective in refining the users’ queries. In only one scenario out of sixty the chatbot was not able to give a satisfactory result; in other cases the goods revealed by the chatbot met all the users’ requirements. It should be mentioned that the chatbot needed 4.7 iterations on average to provide a user with the final list of items.
In our work Δ-measure was used to evaluate the stability of concepts and make the process of query refinement more efective, we also mentioned some other techniques that could be helpful to estimate the importance of the concept, which are some statistical metrics, or machine learning techniques for feature selection. We will try to implement these approaches in our future works.
Overall, this novel model may compete with the traditional IR-chatbots that perform simple queries to the database. Firstly, proposed chatbot adjusts to both the user’s request and the range of items that satisfy user’s criterion; secondly, it helps to reveal essential features, the user might not think about in the beginning, and, finally, it simplifies the decision making process for user, because he needs to observe only small number of the ofered attributes.
As the perspectives for our future investigation we revealed the new task of web search based on unstructured data or text descriptions. We believe that a similar approach can be applied not only to the structured data, when we have the “object-feature” matrix, but also to the task when each object is described by the texts using Pattern Structures and some modifications of Δ-measure. [9] S. O. Kuznetsov, Stability as an estimate of the degree of substantiation of hypotheses derived on the basis of operational similarity, Automatic Documentation and Mathematical Linguistics 24 (1990) 21–29. [10] S. O. Kuznetsov, On stability of a formal concept, Annals of Mathematics and Artificial
Intelligence 49 (2007) 101–115. doi:10.1007/s10472-007-9053-6. [11] S. O. Kuznetsov, S. A. Obiedkov, C. Roth, Reducing the representation complexity of lattice-based taxonomies, 2007, pp. 241–254. doi:10.1007/978-3-540-73681-3_18. [12] M. A. Babin, S. O. Kuznetsov, Approximating concept stability, in: Formal Concept Analysis, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 7–15. [13] A. V. Buzmakov, S. O. Kuznetsov, A. Napoli, Scalable estimates of concept stability, in: C. V.
Glodeanu, M. Kaytoue, C. Sacarea (Eds.), Formal Concept Analysis, Springer International Publishing, Cham, 2014, pp. 157–172. [14] A. V. Buzmakov, S. O. Kuznetsov, A. Napoli, Sofia: how to make fca polynomial?, in: Proceedings of the 4th International Conference on What can FCA do for Artificial Intelligence?-Volume 1430, CEUR-WS.org, 2015, pp. 27–34.