=Paper=
{{Paper
|id=Vol-2972/paper5
|storemode=property
|title=Concept-based Chatbot for Interactive Query Refinement in Product Search
|pdfUrl=https://ceur-ws.org/Vol-2972/paper5.pdf
|volume=Vol-2972
|authors=Elizaveta Goncharova,Dmitry Ilvovsky,Boris Galitsky
|dblpUrl=https://dblp.org/rec/conf/ijcai/GoncharovaIG21
}}
==Concept-based Chatbot for Interactive Query Refinement in Product Search==
https://ceur-ws.org/Vol-2972/paper5.pdf
Concept-based Chatbot for Interactive Query
Refinement in Product Search
Elizaveta Goncharova1[0000−0001−8358−9647] , Dmitry
Ilvovsky , and Boris Galitsky2[0000−0003−0670−8520]
1[0000−0002−5484−372X]
1
National Research University Higher School of Economics, Moscow, Russia
{egoncharova,dilvovsky}@hse.ru
2
Oracle Inc., Redwood Shores, CA, USA
boris.galitsky@oracle.com
Abstract. Nowadays, retrieval-based dialogue engines witness a significant in-
terest in both industry and academic research. It is an important task to create
an automated question-answering engine that may assist a user in the purchas-
ing procedure. In this work, we describe a concept-based chatbot that utilizes a
knowledge model to navigate a user to a subset of relevant objects. The knowl-
edge model is built with pattern structures and organized to manipulate with both
standard numerical and textual attributes describing the observed products. We
provide an experimental evaluation of the introduced chatbot on the Flintkart e-
commerce dataset and compare its performance with the faceted search approach.
Keywords: Query refinement · Information retrieval · FCA · Pattern structure.
1 Introduction
This paper describes ongoing research on creating an information retrieval (IR) chatbot
that can assist customers in a search of suitable objects in the e-commerce database. IR
chatbots have been an area of intense investigation [21, 24] in many spheres, from web
search to electronic libraries. However, conventional search engines are still severely
restricted. For example, when a user needs to refine his or her initial general request,
a typical systems show either all attributes or the most frequently refined ones which
results in the information overload problem and demands many choices to be made until
the satisfactory result is found. Besides, such systems are not able to simultaneously
operate with different types of data, such as numerical and textual ones.
We base our chatbot on utilizing the knowledge model constructed with the theory
of Formal Concept Analysis (FCA) [22] and pattern structures (PS) [7] as its extension,
therefore, further in the paper, we will refer to the chatbot as the concept-based one.
The usage of the knowledge model allows a system to represent all the objects as hier-
archically organized groups (concepts) and the description common for them. Thus, the
chatbot can navigate a user through this model and following the specification or the
generalization path, introduce only the relevant characteristics of a product.
This paper introduces the main aspects of the designed model, specifically, a method
to combine the numerical and textual descriptions which are widely used to describe
objects in the e-commerce datasets (Section 3). As for textual descriptions, we also
Copyright c 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
introduce a new way to define the generalization operation for two textual attributes
that provide a better similarity assessment in comparison to the standard strict match
of the keywords. We describe the bot architecture in Section 4. Finally, experimental
evaluation of the introduced model on the e-commerce dataset is given in Section 5.
2 Related Work
The goal of IR is to find relevant objects that satisfy a user’s request and, probably, refine
it during a search procedure. Nowadays, the most popular IR systems are based on deep
learning (DL) techniques [23, 9, 20]. These models encode the information describing
an object with the neural network forming the object embeddings and, then, find the
closest vectors to a query embedding. In most cases, this approach is applied to the text
data. Lately, there have been some works proposing the neural networks for tabular data
as well [6]. Despite the popularity of these methods, they still suffer from insufficient
data representation, as we need to represent both a short query that reflects only partial
information about the desired object and the whole objects described by many attributes
within a vector of the same length.
FCA can serve as a natural mathematical tool for the knowledge-based semantic IR
systems with the ability to effectively sustain data as a set of robust and hierarchically
connected groups of objects and shared attributes. Traditionally, the studies that apply
FCA to IR consider retrieving information from the large collections of unstructured
documents, which is reasonable due to the analogy between the binary object-attribute
and document-term tables [14]. While the standard IR FCA-based methods have been
applied to the binary data which introduce some restrictions for real-life applications
[15], PS allowed this type of models to be extended to more complex data such as
numbers, graphs, or texts [13, 18, 5].
We claim that introducing a concept model to the e-commerce chatbot is benefi-
cial due to its ability to represent both the numerical and textual attributes of objects.
Moreover, the hierarchical organization of similar object groups can help the chatbot to
effectively refine insufficient users’ requests. However, first, we should define the rules
for computing common descriptions for text attributes. Besides, due to the high compu-
tational requirements for building the concept lattice, we need to understand at which
step of data exploration the concept model should be constructed.
3 Concept Model
A concept model is a principal part of the introduced IR chatbot as it is able to provide a
convenient data representation that reflects the relations among the concepts, data, and
entities. We build the model using PS, let us briefly recall its main definitions.
Formally, PS is defined as a triple (G, (D, u), δ), where G is a set of objects, (D, u )
is a complete meet-semilattice of descriptions and δ → D is mapping of an object to
its description. The Galois connection between the powerset of objects and the ordered
set of descriptions is defined as follows A2 = ug∈A δ (g), d2 = {g ∈ G|d v δ (g)} for
A ⊆ G, for d ∈ D. A pair (A, d) for which A2 = d and d2 = A is called a pattern
concept.
A pattern concept is a pair, where the first element is a set of objects (called pattern
extent) and the second element is the common description (called pattern intent) of
the objects from the set. As in standard FCA, the sub-concept relation is given by the
containment of extents. By defining the specific u for different types of attributes, we
can apply PS to processing complex heterogeneous data. For the introduced chatbot we
have two main types of attributes: the numerical and textual ones.
Numerical Attributes We start building the knowledge model by distinguishing a
subset of homogeneous objects Ah ⊆ G, i.e., the set of objects described by the
high rate of similar attributes and construct PS. A semilattice operation u is defined
attribute-wise. The values of numerical attributes are given by intervals. Let v1 , v2 ⊆ R
be the values of a numerical attribute for two different products. Then, [v1 , v1 ] and
[v2 , v2 ] are their interval representations. The meet of these intervals is defined as
[v1 , v1 ] u [v2 , v2 ] = [min(v1 , v2 ), max(v1 , v2 )]. For nominal attributes, the operation
u is defined as x u y = x if x = y and x u y = ∗ otherwise, where ∗ means “any
value”. The navigation model is constructed in the form of pattern concept lattice that
the chatbot can traverse during communication with a user. The example of this model
for the numerical attributes can be found in github3 .
input : τ {a1t1 }, τ {a2t1 } — textual descriptions (a set of key words) of t1 attribute for
two objects a1 and a2 .
output: τ ({a1t1 }, {a2t1 }) — a common description of t1 attribute for two objects a1
and a2 .
1 foreach key term kta1 of the key terms set τ ({a1t1 }) do
2 foreach key term kta2 of the key terms set τ ({a2t1 }) do
3 if kta1 == kta2 then
4 τ ({a1t1 }, {a2t1 }).add(kta1 );
5 else
6 if similarity(emb(kta1 ), emb(kta2 )) > threshold then
7 τ ({a1t1 }, {a2t1 }).add(kta1 );
8 end
9 end
10 end
11 end
12 return τ ({a1t1 }, {a2t1 });
Algorithm 1: Computing the intersection of two textual attributes
Textual Attributes To process text data we, first, need to define its description, in
our case we use simple keywords. Their usage is motivated by the specificity of the
data we analyze. Textual attributes in e-commerce datasets are usually defined by a
phrase or a sentence. Therefore, it is not necessary to utilize more complex descriptors,
3
https://github.com/lizagonch/Chatbot.git
such as parse trees [19] or parse thickets [4] for such small texts. To calculate common
description for two textual attributes (represented as the set of keywords), we define the
u operation as either a strict match between the keywords or by finding the synonyms
in these keywords sets. The synonymity is assessed via pre-trained word embeddings
(word2Vec [16] in our case). The algorithm 1 presents the procedure to calculate the
intersection for two textual attribute descriptions.
4 Chatbot Overview
The idea of the introduced model is as follows, a user starts a search with an imprecise
request, the search engine interactively refines a user’s request by moving him or her
down or up the lattice (concept model). The concept lattice is built using Close-By-One
algorithm [1]. The overall system architecture is shown in Figure 1. At each turn of the
dialogue, the user’s utterance written in natural language goes through the NLP pipeline
where sentence pre-processing is performed. This module is also responsible for iden-
tifying numerical attributes a user wants to refine and textual restrictions imposed on
the product. Thus, at the output, we get the user’s query description dq . Let us consider
each component in more detail.
Fig. 1. System architecture
4.1 NLP Pipeline
We use Stanford CoreNLP toolkit [12] to perform sentence splitting, tokenization, and
lemmatization. Then, the system reveals the restrictions on the numerical attributes.
This part is performed with a predefined set of rules that determine attributes names and
the values required by the user. Having retrieved these restrictions, we run the keyBERT
model to return the set of keywords representing the user’s request.
4.2 Intent Classifier
The proposed IR bot operates using the compiled hierarchical lattice-based knowledge
model. It means that the system can navigate a user up (in case of generalization intent),
or down (refinement intent) the lattice. If a user wants to change the direction of a
search, the bot should navigate him or her to another candidate concept at the same
level of the concept lattice, where the level is the shortest way from the root concept
to the current one. If a user clarifies some features proposed by the chatbot, then the
chatbot moves in the right direction. Otherwise, asking to return on the previous step
corresponds to generalization intent. We use manually constructed regular expressions
to recognize the navigational intent.
4.3 Search Procedure
After identification of the intent, the system navigates a user through the knowledge
model. Based on the user’s intent, the bot provides various procedures to query pro-
cessing. (i) If the user wants to refine his current position, the bot finds all most specific
concepts that satisfy an input query description and updates the State Table with new
candidate concepts. (ii) In the case of update intent the bot returns the user to the parent
concept of the current (Ai , di ) concept. (iii) Change of interest makes the bot return to
the stack of promising concepts (State Table) and moves to the next candidate concept.
All candidate concepts in the State Table are ranked based on the stability measure
[2, 8, 11], and each feature in the concept intent is assessed with respect to its diversity.
The most stable concepts are introduced to the user first, whereas the most variable
characteristics are proposed to the user for further refinement.
5 Experiments
We present the preliminary experiments to compare the concept-based chatbot perfor-
mance with the faceted search4 technique which is a standard approach for e-commerce
IR. The experiments are performed on the publicly available Flipkart dataset5 that con-
tains information about more than 40000 objects from the e-commerce website. To
compare the chatbot with the faceted search, which is not able to process textual data,
we have retrieved 100 objects belonging to the category ‘Computers – Laptops’ de-
scribed only by the numerical attributes. To measure the effectiveness of the proposed
u operation for textual attributes we use the same concept-based bot, but define the gen-
eralization operation as the strict match of the keywords corresponding to the textual
attributes. For this experiment, we have retrieved 300 objects belonging to the ‘Cloth-
ing – Jeans’ category. The motivation for choosing these small datasets is that both
the faceted search and the IR-chatbot should be launched after a user found the specific
category of products that he or she is interested in that usually include up to 500 objects.
To assess the model performance we calculate the average number of iterations (IN)
a user needs to achieve a satisfactory result. The lower this number is the faster a user
finds relevant objects. Average Precision (AP) measures how many times during the
dialogue a user had a refinement navigational intent. We also evaluate the number of
cases where a user was not satisfied with the response of the bot and asked it to move
in another direction (Unsatisfactory Rate (UR)).
4
https://apex.oracle.com/en/
5
https://data.world/promptcloud/product-details-on-flipkart-com
So far, we have not conducted the conversation of the bot with real customers, thus,
in a preliminary experiment, we generated 60 random scenarios of possible users’ re-
quests. The scenario takes the form of a few relevant features and a range of their values
that the user should sequentially introduce to the system. Table 1 presents the results of
the experimental evaluation.
Table 1. Comparison of the knowledge-based search with the faceted search.
Laptops (only numerical attributes) Jeans (+ textual attributes)
Model AP UR IN AP UR IN
Concept-based bot 0.7 0.24 5.6 0.72 0.14 6.6
Faceted search — 0.31 6.2 — — —
Concept-based bot
— — — 0.68 0.25 8.6
(key words-strict match)
AP and UR metrics indicate the ability of the bot to rank the promising pattern
concepts and retrieve relevant features for refinement. The obtained results show that in
nearly 70% of cases attributes introduced by the chatbot were assessed as significant.
While, in almost 25% of cases in the “Laptops” category, a user had change of direction
intent. The main metric evaluating the effectiveness of the search engine is the average
number of dialogue turns (or clicks for the faceted search) that a user performed to
find the set of items that are needed. In our experiments, this metric is in favor of
the chatbot, 5.6 versus 6.2 respectively. For textual data processing, the approach that
applies embeddings techniques to u operation improves the performance of the model
and makes a search procedure more precise (6.6 versus 8.6 dialogue turns).
6 Conclusion
In this paper, we have introduced an IR chatbot that utilizes the concept-based knowl-
edge model to help users in finding a particular item in the e-commerce database. In
comparison to a standard search engine, this system can operate with both structured
data and textual descriptions that can also be obtained from any external resource.
We have compared the performance of the proposed model with that of the faceted
search using the small product database retrieved from the online store. In this work in
progress, we have not yet compared the performance of the model with the current state-
of-the-art IR systems and other promising query enrichment FCA-based techniques
[10, 17, 3], however, the obtained results based on the artificially generated scenarios
of user-machine interaction has shown that the number of steps required by the pro-
posed model is less than the one required by faceted browsing. In the future, we plan
to add more functionality to the model, such as more advanced processing of textual
information (e.g., a pre-defined set of syntactic patterns could be exchanged by the DL
conversational engine) and more intelligent search of relevant attributes that should be
introduced to the user. This can be achieved by encapsulating the history of users’ pur-
chases.
References
1. Andrews, S.: A partial-closure canonicity test to improve the performance of CbO-type al-
gorithms. Lecture Notes in Computer Science 8577 (2014)
2. Babin, M.A., Kuznetsov, S.O.: Approximating concept stability. In: Proceedings of ICFCA
2012. pp. 7–15 (2012)
3. Bendella, M., Quafafou, M.: Patterns based query expansion for enhanced search on twitter
data. In: CEUR Workshop Proceedings. vol. 2378 (2019)
4. Galitsky, B.A., Ilvovsky, D., Kuznetsov, S.O., Strok, F.: Finding maximal common sub-parse
thickets for multi-sentence search. In: Graph Structures for Knowledge Representation and
Reasoning. Lecture Notes in Computer Science. vol. 8323 (2014)
5. Hartmann, J., Stojanovic, N., Studer, R., Schmidt-Thieme, L.: Ontology-based query refine-
ment for semantic portals. In: Lecture Notes in Computer Science. vol. 3379, pp. 41–50
(2005)
6. Katzir, L., Elidan, G., El-Yaniv, R.: Net-DNF: Effective deep modeling of tabular data. In:
Proceeding of ICLR. vol. 125 (2021)
7. Kuznetsov, S.: Pattern structures for analyzing complex data. In: Rough Sets, Fuzzy Sets,
Data Mining and Granular Computing, 12th International Conference, RSFDGrC 2009.
Delhi, India
8. Kuznetsov, S.: Stability as an estimate of the degree of substantiation of hypotheses derived
on the basis of operational similarity. Nauchno-Tekhnicheskaya Informatsiya, ser. 2 - Infor-
matsionnye Protsessy i Sistemy pp. 21–29 (1990)
9. Li, J., Liu, C., Wang, J., Bing, L., Li, H., Liu, X., Zhao, D., Yan, R.: Cross-lingual low-
resource set-to-description retrieval for global e-commerce. Proceedings of the AAAI Con-
ference on Artificial Intelligence 34 (2020)
10. Lungley, D., Kruschwitz, U.: Automatically maintained domain knowledge: Initial findings.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial In-
telligence and Lecture Notes in Bioinformatics). vol. 5478 (2009)
11. Makhalova, T., Ilvovsky, D., Galitsky, B.: Information retrieval chatbots based on conceptual
models. In: Proceedings of International Conference on Conceptual Structures. pp. 230–238.
Springer (2019)
12. Manning, C., Surdeanu, M., Bauer, J., Finkel, J., Bethard, S., McClosky, D.: The stanford
CoreNLP natural language processing toolkit. In: Proceedings of 52nd Annual Meeting
of the Association for Computational Linguistics: System Demonstrations. Association for
Computational Linguistics (2014)
13. Messai, N., Devignes, M., Napoli, A., Smaı̈l-Tabbone, M.: Many-valued concept lattices for
conceptual clustering and information retrieval. In: Proceedings of ECAI (2008)
14. Messai, N., Devignes, M.D., Napoli, A., Smail, M.: Concept lattices and ontologies to query
a directory of biological data sources (bioregistry). INFORSID 2005: Actes du XXIIIeme
Congres Informatique des Organisations et Systemes d’Information et de Decision (2005)
15. Messai, N., Devignes, M.D., Napoli, A., Smail, M.: Using domain knowledge to guide
lattice-based complex data exploration. In: Proceedings of the 2010 conference on ECAI
2010. pp. 847–852 (2010)
16. Mikolov, T., Sutskever, I., Chen, K., Corrado, G.S., Dean, J.: Distributed representations of
words and phrases and their compositionality. In: Advances in neural information processing
systems. pp. 3111–3119 (2013)
17. Pattison, T.: Interactive query refinement using formal concept analysis. In: International
Conference on Concept Lattices and Their Applications (2018)
18. Priss, U.: Lattice-based information retrieval. Knowledge Organization 27 (2000)
19. Punyakanok, V., Roth, D., Yih, W.T.: The necessity of syntactic parsing for semantic role
labeling. In: Proceedings of IJCAI International Joint Conference on Artificial Intelligence
(2005)
20. Song, S., Wang, C., Chen, H., Chen, H.: TCNN: Triple convolutional neural network models
for retrieval-based question answering system in e-commerce. In: The Web Conference 2020
- Companion of the World Wide Web Conference, WWW 2020 (2020)
21. Tunkelang, D.: Dynamic category sets: An approach for faceted search. In: Proceedings of
ACM SIGIR. vol. 6 (2006)
22. Wille, R.: Restructuring lattice theory: An approach based on hierarchies of concepts. Or-
dered Sets. NATO Advanced Study Institutes Series 83, 445–470 (1982)
23. Yilmaz, Z., Wang, S., Yang, W., Zhang, H., Lin, J.: Applying BERT to document retrieval
with Birch. In: Proceedings of IJCNLP 2019. pp. 19–24 (2019)
24. Zhang, L., Zhang, Y.: Interactive retrieval based on faceted feedback. In: Proceeding of the
33rd international ACM SIGIR conference on Research and development in information
retrieval - SIGIR '10. ACM Press (2010)