In most e-commerce platforms, search system supports free text keyword based queries. These queries can be very open ended. In contrast with traditional web search engines, recall set for ecommerce platform is usually constrained by the underlying inventory of products that are available in stock. This demand and supply gap leads to null or sub-optimal query results, which in turn, leads to a bad user experience. In this paper, we propose a query substitution approach based on semantic comprehension of
• Applied computing → Online shopping;
In an online shopping portal, user query typically is a salad of words. A search engine is responsible to process this query and retrieve relevant results for the user to explore. E-commerce search is catalogue based and rely on precise descriptions of products. In contrast to web searches, zero result searches are more probable Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).
WOODSTOCK’97, July 1997, El Paso, Texas USA © 2016 Copyright held by the owner/author(s).
ACM ISBN 123-4567-24-567/08/06. . . $15.00 https://doi.org/10.475/123_4 in e-commerce search as user queries are quiet descriptive and expected results are very specific. Also, recall set is constrained by the availability of products in stock.
Zero results leads to buyer frustration and potential loss in revenue. To counter this problem, numerous techniques have been developed which generate query suggestions on the basis of user click-stream and session data. Query reformulation or query rewriting is performed either when the user query is an imperfect description of the information needed or information retrieval engine fails to understand the query completely.
Null queries are most unique and most engines do not possess enough intelligence to handle them [5]. Query transformation or reformulation is seen as rewriting a query to retrieve a set of intended results. It can be achieved by query expansion and query substitution. Query expansion uses techniques like pseudo-relevance feedback and query relaxation or deleting query terms [3]. Query substitution uses content based understanding [1, 4, 8, 10]. These techniques modify the query to make it nearer to the content intended. Hence they are more relevant to web searches where the documents are elaborate and accurate mapping of user query to appropriate content is needed.
We define query substitution as an aid for the user to get the closest results when there is no matching content available for the exact query. We perform query Expansion by dropping irrelevant terms and query term substitutions using Entity Afinity Relationship Graphs to generate appropriate query suggestion.
Our information retrieval system is a search engine for
fashion catalog with more than a million products. A user in any
ecommerce platform either casually browses the catalogue or intends
to purchase a targeted product. Search is an eficient for the latter.
The technique discussed in this paper is specifically designed for
improving search in fashion domain. We present a novel approach
of query suggestion by query substitution pertaining to human
fashion interpretation. While working in this domain, we deal with
numerous complexities like the following:
(
So it is required to transform the query while understanding
preferences and intents of the users.
(
Rest of the paper is organized as follows. We present the related work for query reformulation in the next section. We briefly describe how our search system works in section 3. Section 4 covers the architecture of Query Substitution framework followed by a detailed look at Entity Afinity Relationship Graph (EARG) in Section 5. Experiments and Results are explained in section 6. 2
Handling zero result queries to improve the recall of search system in e-commerce is explored by many researchers. Most of the work utilizes click-stream and user session data. In [5] time-based relevance feedback is used to improve the fidelity of rewrites. The algorithm performs query relaxation by searching the original query against a database of expired items, using the meta-data of matched expired items to constraint the rewritten query, and get more precise results while matching against a database of active items.
In [2] query is transformed using re-query feedback. User query reformulation activities in the form of deletion, insertion and modification of terms in the query are used to create term-transition graphs which in turn is used for suggesting. In contrast to this approach, we discuss a graphical representation of terms in the query and afinity relationships among them, extracted from the pair of attributes explored together in a session.
Another piece of work [7] discuss context aware query suggestions. Similar queries are grouped into concepts and suggestions are provided based on the concepts. However, researches have shown that [6] the zero recall queries are close to being unique. Even the most popular zero recall queries do not repeat more than tens of thousands of times within a month. But the most popular non-zero recall query repeats more than millions of times. Hence we cannot rely only on query specific models. The implicit preferences of users, what attributes are explored interchangeably, insights of domain from users activities are a few factors that can contribute in building a query suggestion system closer to how a user himself might think.
Any search system has endless data in the form of user queries and clicked results in a session. This data is an excellent source of information and can be used appropriately to accurately and eficiently retrieve relevant results[9, 10].
In this paper, we focus on improving the recall for zero result queries
in fashion e-commerce using user click-stream and session data.
Our contributions are:
(
Input to the search system is user queries in the form of free text keywords, seeking fashion products to buy or explore. Even-though, the queries are often targeted at what the user is looking for, there is a tendency to make a purchase even if close matches or variants are presented. In such a scenario, it is important to correctly interpret user intents and preferences and present a suitable set of results. Consider the example,
“Nike black shoes without laces" It appears that user here intends to buy a casual shoe which should not have laces and is black in color, preferably of brand Nike. There is a lot of information a user provides in this query. It is important to parse the query, understand it, disambiguate it, and then appropriately retrieve the results.
Figure 1 demonstrates the overview of our search system. The user query is parsed, sanitized, analyzed and annotated as a part of Query Processing. These annotations in the output annotated query after query processing are from a finite set of tags that categorize all fashion terms into types of products and various attributes. Unknown words are not annotated. Results are retrieved firing the annotated query. If we do not have suficient number of results to display, we transform the query in query substitution engine and again execute the query. The new set of results are then displayed to the user.
Substitution algorithm ensures suficient number of relevant results for the user. This algorithm is explained in the next section. 4
Before elaborating upon the substitution, it is important to understand the structure of a user query. Avery user query has a primary intent. We define primary intent, as an entity which cannot be modified. In most cases, it is the article type or category which the user is looking for. In addition to this, an attribute set is present in that describes the primary intent. Primary intent also serves as the context for attributes while performing substitutions. In case, no primary intent is identified, substitutions are performed in global context. This will be elaborated in the following sections. In the previous example, “Nike black shoes without laces", ‘shoes’ is the primary intent as it is clear that the user intends to buy nothing else but shoes. Other attributes describing ‘shoes’ can undergo modifications depending on their respective importance. Hence, ifrst step for substitution is prioritizing these attributes on the basis of their popularity. If there is a primary intent present and is identiifed, attributes are prioritized on contextual popularity else global popularity. Here, brand ‘Nike’, color ‘black’, and attribute ‘slip-ons’ (annotation for ‘without laces’) are assigned priorities as per the general user preferences and tendencies to compromise certain attributes. We describe computation of priorities computations in the next section. For the sake of understanding the algorithm, lets assume the Popularity(Nike)<Popularity(Black)<Popularity(slip-ons). As Figure 2 represents, how we substitute the terms in order of popularity and generate a list of substitutable queries.
Assuming that attribute Nike has least normalized popularity for
shoes, we search for its substitutes in context of shoes. Substitution
is performed in three simple steps:
(
Outcome of this step is a list of substituted queries sorted in order of closeness to the original query. The top most candidate is picked from the list and result is displayed to the user.
Query expansion is a fast and efective way of handling zero result queries. List of attributes are sorted in order of popularity and the least popular attribute is simply dropped. This is an ideal treatment for a low recall search system but at the same time compromises with relevance of products. Consider a query ‘Nike skirts’. User here is looking for skirts which are sporty as ‘Nike’ is a brand, ofering products mostly pertaining to sports. The explicit intent is a ‘skirt’ of Brand ’Nike’, implicit intent is a ‘skirt’ used for sports.
Query Expansion will get rid of Brand ‘Nike’ and display all the skirts in the catalog. Query Substitution, in contrast, will look for other brands of similar nature and show the results which are much more relevant.
A query transformation system which expands or substitutes appropriately is an ideal way to have a high recall with relevant results. The query should be expanded when the attributes are in no way relevant or do not help us to derive any hidden intent. Any attribute of value should be utilized to improve result relevance. 5
Entity Afinity Relationship Graph is a weighted directional graph created using everyday user preferences while exploring products on the fashion portal. This section describes the domain, data used, and algorithm used to create these graphs. 5.1
EARG is the representation of universal fashion entities, and the inter-relation between them, established from user sessions comprising of product exploration events.
Figure 3 shows the hierarchy of entity types in EARG. Nodes in
the graph can broadly be categorized into 3 types. figure 3
(
Each node is attached with a popularity score which is used to compare the importance of each attribute in a query when no primary intents are identified.
Edges represent inter-relationship among the nodes. There are 3
types of relationships that can exist:
(
These are weighted edges from global attributes and article
type specific attributes to Product category nodes (master
Category, sub-category and article types). Weights represent
the popularity of global or article type specific attributes
given the product category context to which the edge is
connected.
(
These are weighted edges between two nodes of same type.
For example ‘Nike’ is connected to ‘Reebok’ as both are
sports brands. Weights represent the strength of afinity.
(
In Figure 4, solid arrow represents article specific Popularity. i.e. popularity of ‘Nike’ as a brand when article type is ‘casual shoes’ is 0.0657. The dashed arrows represent afinity between two attributes of same type. In this case, it is brand to brand afinity. The above diagram shows top 5 similar brands to ‘Nike’ and ‘HRX’, where weights on the edges is the afinity score. ‘Nike’ has maximum afinity to ‘adidas’ with a score of 0.0362 and least afinity to ‘HRX’ with a score of 0.0088. Similarly, ‘HRX’ has maximum afinity to ‘Roadster’ with score 0.0235 and least afinity to ‘Mast & Harbour’ with score 0.0079.
In Figure 5, dashed arrow represent top 5 Article specific afinity scores for Brand ‘Nike’. For example, for article type ‘casual shoes’, Nike has maximum afinity to ‘Puma’ and minimum afinity to ‘UCB’ where as when the article type is ‘sports shoes’, ‘adidas’ is the most similar brand and ‘ASICS’ is least similar.
Every information captured in the above graph helps in making decisions during substitution of query terms. As described in the previous section, global popularity is used to prioritize attributes when no primary intent is found, Article type specific popularity is used otherwise. "Global afinity" and "Article type specific afinity" are used to find substitutions for attributes. 5.2
User session data is collected from the online e-commerce portal of Myntra Designs Private Limited. Every user exploring the fashion store is a part of a session. Within a session, multiple products are explored (clicks and product views). These products can be pivoted upon a single intended purchase. The user is taken from list page to product display page upon click on any specific product. This event is captured for every user. The basic and reasonable assumption here is that within a session, user clicks or views products which are similar to each other. This can help us in establishing the afinity relations and popularity of various products and its attributes. Session data needs to be pre-processed in order to get rid of numerous useless sessions.
(
(
Popularity of an attribute is the measure of its importance among other attributes of similar type. Here, Popularity(An ) is the popularity value of a given attribute An . ‘session’, as described above is a set of consecutive searches by a particular user for a given article type. Ai j is is the number of times attribute Ai is viewed in jth session. Attribute is a set of all possible values of attributes of same type.
Table 1 is a sample data for a few brands explored for ‘shoes’ by various users in the respective sessions. Article type specific popularity of Nike, Popularity(BrandN ike ), for when user is looking for shoes, can be computed as follows:
Popularity(BrandN ike ) = 4180 + 120 + 102 + 188 + 158 5 To compute the global popularity of BrandN ike , similar computations will be done across all the products, irrespective of what is the article type.
Afinity between two attributes represents how confidently we can substitute one attribute with another attribute of the same type in a global context or for a given article type. Note that this is not similarity between attributes, but what is the possibility that a user looking for one attribute can compromise and go for another attribute.
Af f inityAn →Am = µ 1/2 An1A+nA1 m1 , An2A+nA2 m2 , ..., AniA+nAi mi Here, Af f inityAn →Am represents the Afinity of an attribute An to attribute Am . sessionW ithAm > 0 are the sessions where Am is explored at least once. µ 1/2 is the median of values from all the sessions. We prefer median over mean as the data can be skewed depending on the availability of products. We measured the performance of query substitution basis product discovery and products sold through typed search for a static cohort of 1Mn users on a e-commerce platform of Myntra Designs Pvt Ltd. Experiment base was divided into an equal number of users in test and control groups. Our new method(test) was compared with the fashion agnostic query expansion(control).
The experiment was repeated for three weeks to confirm the performance of the method. The statistical significance of the results was measured by p-value of a test on null hypothesis H0.
H0: The diference in metrics between test and control groups is caused by random variation.
Product discovery is measured basis clicks on catalog exposed
through search while keeping a close eye on recall basis zero results.
We observed following improvements between the two groups:
(
To measure the impact of the trade-of between recall and product clicks, the percentage of products sold through search was used. It kept a check on the relevance of the results. Final purchase by customers is the biggest testament to the fact that they found what they were looking for. This is a key criterion for query substitution to succeed and suggest that the search results presented are actual substitutes for user queries. substitution. Theses queries were then re-executed in an identical ofline setup with query substitution on. 61% of these queries successfully retrieve relevant results. Few examples of Query transformation seen in this experiment, in the form of expansion as well as substitution are shown in table 6.
Table 6 clearly shows how a brand is substituted with a similar brand within the respective contexts. In the first example, ‘Fossil’ is the brand where the user finds leather bags similar to what they get in ‘Michael Kors’ where as for someone looking for “Elle handbags", ‘Forever 21’ is the brand where the user is able to find what is needed. In another example, user is looking for ‘aldo leather bags’ which are not available and we show ‘aldo synthetic leather bags’ as they are not currently available in inventory.
Analysis of the misses in the experiment shows that a significant portion of these queries are either inappropriate for fashion domain (for e.g. “fidget spinner",“red chaos", “vegetable cutter" etc.) or are extremely miss-constructed for the system to understand. In such cases, zero result is the most relevant result.
Next best results have an extensive use of query term substitutions. The user query is substituted when we do not get any results from catalog to show to the user. In such a case the extent of query modification should be limited. Contrary to this, if exact product match to user’s query has insuficient results or the modified and original query are diferent beyond a threshold, multiple query terms are substituted to create a list of next best results for the users to optionally pick any query as per their preferences.
We have presented an ingenious approach, dynamic query substitution, to improve the search results in the context of fashion catalog. Our method identifies a primary intent of the user and pivots on this core idea to provide substitute products. The method also ensures to capture all the information assessed from user query instead of unintentional dilution of information in other methods like query expansion. The candidate terms for substitution are identified basis EARG relations that capture the users’ intent over multiple sessions. We have shown through experiments on a large user base that this method is significantly efective than the existing methods in improving the clicks and sell through of products. Dynamic query substitution has many practical applications as well such as showing the next best results in absence of enough exact matching products in fashion e-commerce.