Query Understanding is a semantic search method that can classify tokens in a customer's search query to entities such as Product, Brand, etc. This method can overcome the limitations of bag-ofwords methods but requires an ontology. We show that current ontologies are not optimized for search and propose a simplified ontology framework designed specifically for e-commerce search and retrieval. We also present three methods for automatically extracting product classes for the proposed ontology and compare their performance relative to each other.
• Computing methodologies → Information extraction; Ontology engineering;
Search plays a vital part in any e-commerce site and a poor search
system leads to customer frustration, which negatively afects both
retention and conversion. Most e-commerce sites employ a
bag-ofwords search method which simply matches tokens in a customer’s
search query with relevant fields of SKUs (stock keeping unit but
used here to describe any item sold by the site). This system is easy
to implement specially with solutions like ElasticSearch [
SIGIR eCom 2018, July 2018, Ann Arbor, Michigan, USA © 2018 Copyright held by the owner/author(s). camera” may produce the same result if prepositions are ignored as stopwords. There are ways to augment the bag-of-words search system with a category pinpointing (or prediction) model, bigrams, etc. to improve the recall. However, this approach requires a deep category tree with leaf nodes as product types and an accurate categorization model, both of which could be an issue given a large catalog.
A better approach to search is to use a query understanding
system to understand the customer’s search intent [
We propose a simplified ontology framework specially designed from a search and retrieval perspective that contains three toplevel concepts - Product, Brand and Attribute and five slots (or properties) - synonyms, attributes, primary_attributes, brands and default_product. We show that these three entity classes along with ifve slots can provide relevant recall for a customer’s search query. We further discuss this ontology in Section 2 and provide insights into why each entity type and slot is necessary and how they help in retrieving relevant results.
Our contributions in this paper are creating a product ontology designed specifically for search and providing three methods to automatically extract Product concepts for this ontology. We discuss this ontology in detail in Section 2. We provide an overview of the ifeld of Ontology learning in Section 3 and discuss our methods to extract Product concepts in Section 4. Finally, we present our conclusions in Section 5. 2
An ontology is a formal explicit description of a domain by
identifying classes (or concepts), slots and slot restrictions between classes
for a particular domain [
Work has also been done on ontologies that are focused more on
the catalog side [
A Product is defined as the atomic phrase that describes what the customer is looking for. Consider an example, “white chair with ottoman”. Here, the customer is looking to buy a chair. It is preferable if the chair is white in color and comes with an ottoman but these requirements are secondary to the primary requirement of it being a chair. If such a chair is not available, the customer is more likely to buy a chair in a diferent color or one that does not come with an ottoman but is less likely to buy a white sofa with ottoman even though it satisfies two requirements out of three. Any specialized product type like folding chair must be stripped down to its most basic form chair. There are exceptions to this rule, for example, a bar stool is a specialized type of stool and ideally we should strip it down to its most basic form stool but many customers use the term “barstool” (single term without spaces) to describe it. The NERC system has to be able to classify this term to a product and hence we include the term “barstool” as a Product in our ontology with the synonym “bar stool”. The class barstool is a sub-class of the class stool because every barstool is ultimately a stool. This parent-child relationship also helps during recall because if the customer searches for “stool”, the search system will include all stools including barstools in the recall. It should be noted that atomic does not imply a single-word token because many multiword tokens like air conditioner and onion rings are atomic. We use a combination of our query and SKU understanding systems along with user data to provide suggestions for parent-child relationships and synonyms (or variations). However, describing this method is beyond the scope of this paper. 2.2
Attribute is defined as an atomic phrase that provides more information about an item. Consider an example “white wooden folding adirondack chair”. Here, we classify the term chair as a Product and we can classify the remaining terms (white, wooden, folding and adirondack) as Attributes. This gives us a lot of flexibility during recall. Initially, the search system can restrict the recall by filtering out any SKUs that do not match the product type and then boost SKUs by the number of matching attributes. In case of our example, we would restrict the recall to be chairs of all types and then boost those SKUs that match the attributes (white, wooden, folding and adirondack). A SKU that matches all attributes will have a higher score (and placed on top of the recall) than those that match fewer attributes.
Attributes can be subclassed as Color, Material, SleeveType, etc. depending on the category. We found that only a subset of Attributes are relevant for search purposes. An attribute like Country of Manufacture may be a valid subclass but it can be argued that it is not very important for search purposes. Since our aim is to create a simplified ontology for search, we restrict attribute subclasses to what is actually important for search. This makes the system much more maintainable. The range of most attributes are values from an enumerated set but some attributes like Screen Size may have numeric values along with a unit of measurement like inches, cm, etc. Such numeric values can be normalized using simple rules (1 inch = 2.54 cm) so that more relevant SKUs can be recalled for a given query even if they have units from diferent measurement systems. It is not necessary that numeric values in the query and SKU to match exactly. We compute the diference between corresponding numeric values of the query and SKU and apply a boost that is inversely proportion to the diference. For example, a query: “45 inch tv” will match SKUs for 43 inch TVs (higher boost) as well as 49 inch TVs (lower boost) 2.3
A Brand is defined as a phrase that provides more information about the manufacturer of the item. Samsung, Calvin Klein, etc. are examples of brands. Brands are important because they capture information about the preferences of the customer but are not essential in defining the recall. The search system tries to honor the customer’s preference regarding the brand by boosting SKUs that match the brand specified in the query. This scheme ensures that the search result includes SKUs from other brands albeit at a lower position compared to SKUs that match the brand in the query. We observed that in some cases customers tend to use the brand name as a synonym for a product, for example, “q-tips” to denote cotton swabs and “kleenex” to denote tissues. This type of behavior is common for a subset of brands that have high brand equity and are taken to represent the product itself. We wanted to respect the customer’s preferences while still providing them with a wide range of similar products from other brands and so we introduced the default_product relation, which maps these finite subsets of brands with their default Product nodes. This relation then allows the NERC system to map the query “kleenex” to kleenex := Brand, tissues := Product and have the flexibility to present relevant SKUs from other brands at a lower position in the recall. Currently, we do not support a parent-child relationship between brands (for example: Nike) and sub-brands (for example: Nike Air). and treat each sub-brand as a variation of the original brand. 2.4
We propose five slots or properties - synonyms, attributes, primary_attributes, brand and default_product and show how they can be used to recall relevant SKUs for a given query. The synonyms slot indicates synonyms of a given class and are typically used to address alternate phrases used to describe the same item. The synonyms slot exists for all classes in our ontology. The attributes slot has the Product class as its domain and the Attributes class as the range. It helps in specifying all relevant attributes for a given SKU. Since we insist on atomic products, this slot helps us in distinguishing relevant SKUs from irrelevant SKUs in the recall. Consider the two queries “Dining Chair” and “Outdoor Chair”, which refer to two very diferent products even though they are both chairs. The NERC system is able to extract the attributes dining and outdoor for those two queries and is able to boost SKUs that match these attributes to the top of the recall. Thus, the customer is presented with relevant SKUs in each case even though the product type of both queries is the same. Consider a search query “cotton shirt”, where the NERC system is able to extract the material cotton. As discussed previously, the system will retrieve all shirts and automatically boost cotton shirts so that they appear the top of the recall. Let us assume that there are two SKUs - one shirt made of 100% cotton and the other shirt made out of 95% polyester and only 5% cotton. If there is no notion of primary_attributes both SKUs will receive the same attribute boost and will be considered equally relevant. The primary_attributes is a special slot that maps a Product with a single Material or Color subclass. In case of the previous example the primary_attribute will point to cotton := Material for the first SKU and polyester := Material for the second. This slot helps increase relevancy by boosting only SKUs that match the corresponding primary color or material.
The Brands slot has the Product class as the domain and the Brands class as the range. It defines the manufacturer for a given SKU. As mentioned previously, the default_product slot helps in assigning a product to a small set of brands like Kleenex that are used synonymously with products. Both slots help increase relevancy by boosting all SKUs that match the extracted brand from the query but without sacrificing the ability to show SKUs from other brands at lower positions on the search page.
Our current implementation of ranking SKUs is rather simple providing fixed boosts when products, brand and attributes from the query match products, brands and attributes in the SKU. In future, we will use these matches in conjunction with a ranking model to further improve relevancy. 3
The task of building an ontology is a time consuming and expensive
task and usually involves a domain expert. Techniques that support
ontology engineering and reduce the cost of building and
maintaining ontology are required to ensure that this task is scalable.
Ontology learning can be thought of as data driven methods that
support building ontologies by deriving classes and meaningful
relations between them. Petucci et al [
The term extraction layer is the lowest layer in the cake. It aims to
learn the relevant terminology of the domain. A naive approach
is to just use term frequencies assuming that relevant concepts
are also most frequent. However, other sophisticated methods like
TF-IDF [
The next layer is the synonym extraction layer, which deals with
extracting synonyms for the terms identified in the previous layer.
Synonyms can be extracted using a distributional representation of
words, which claim that similar words share similar contexts [
The third layer is the concept formation layer, which provides a
definition of concepts, their extension and the lexical signs which
are used to refer to them. The fourth layer is the concept
hierarchy layer, which deals with inducing, extending and refining the
ontology hierarchy. This task can be accomplished by methods
like matching lexico-syntactic patterns as demonstrated by Hearst
in [
The fifth and sixth layers deal with Relations, which is the task of
learning relation labels (or identifiers) as well as their
corresponding domain and range. Some common methods include finding
co-occurrence between words as proposed by Madche [
We describe three methods (Token Graph Method, Augmented Graph Method and LSTM-CRF method) that can be used to automatically extract atomic Product entities from a customer’s search query. Two of these methods may also be extended to extract relevant attributes and brands from the search query as well as from product titles. We then compare the performance of these three methods relative to each other.
We assume that there exists a bipartite graph G : q 7→ S that maps a customer’s search query q to a set of clicked SKUs S. This graph may be further augmented by including SKUs that were added to cart or bought. Search queries and SKUs are represented by nodes in the graph and an edge between a query and a SKU indicates that a customer searched for the query and clicked on the corresponding SKUs. The weight of the edge indicates the strength of the relationship between the query and the SKU and is modeled using number of clicks between the query and the SKU aggregated over a certain length of time. There are no edges between queries or between SKUs. Very broad queries like “cheap” or “clothing” either do not contain any products or contain very generic product terms and add noise to the data. We use entropy of a query across diferent categories to determine if it is broad and remove it from the graph. We also remove queries that are just brands from the graph and query-SKU pairs that have edge weights less than some threshold (T ). Finally, we apply a stemmer to perform stemming for terms in the query. Let G ′ denote this cleaned bipartite graph. The task can be formulated as follows: Given a cleaned bipartite click graph G ′, compute a sorted list of Product sub-classes that are atomic and relevant for that category. We present three methods to create the sorted list of Product classes and compare them. 4.1
This method is a very simple unsupervised method for extracting relevant products from a customer’s search query and can be applied to any category without any previous data. Let C = {q0, q1, . . . , qn , s0, s1, . . . sm } be a connected component in the bipartite graph G ′ mentioned previously. Let Q = {q0, q1, . . . , qn } be a set of queries in this connected component and we can assume that all of them are related to each other because they share some of the same clicked SKUs. Let us assume that we can detect prepositions in the query and have removed them and all words after it from the query. Each token in the query is either a brand, product, attribute or other (part number, stopword, etc.) and we can create a new graph Gtoken where each token is a node and there are edges between adjacent tokens. Figure 3 shows the token graph Gtoken for the query set {women dress, white dress, DKNY sleeveless dress white}. Most often, the product token is the last term in the query before any prepositions and thus it is the node that maximizes the ratio NoN+iNi , where No is the number of outgoing edges and Ni is the number of incoming edges for the node corresponding to the token. If the search query contains just a single token, we set ni = no = 1. We can further improve precision by requiring that Ni ≥ T , where T is some threshold. There are obvious exceptions to the rule, for example the search query: “DKNY sleeveless dress white” where the product dress does not appear in the end of the query. However, we assume that such cases are rare and assume that aggregating this process over all related queries takes care of the occasional exception. We can generate a potential product from each connected component and aggregating over all connected components gives us a potential list of products.
The graph method in the previous section works pretty well but makes a very strong assumption that the product always appears towards the end of the search query. It is also very aggressive in removing the preposition and all tokens after it. For example, it will convert the query ‘’seven for all mankind skinny jeans” to “seven”, which is obviously wrong. Finally, it is oblivious to the parts-of-speech of the terms.
Typically, product words are nouns (television, shirt, etc.) and we
can take advantage of parts-of-speech tags to improve the
accuracy of the system. One option is to use global parts-of-speech
tags from wordnet [
We want to capture the local graph information discussed in the previous section. This can be done by creating the local graph and computing the number of incoming and outgoing edges for each ni term in the query. Let viG = [ni , no , ni +no ] denote a vector that captures local graph information for the ith term. Here, ni indicates the number of incoming edges for the node denoting the term in the local graph and no indicates the number of outgoing edges for the same node.
Let viN = N − i denote a scalar describing the position of the ith term in the search query, where N is the number of terms in that query. This vector helps the model prefer later words in the query as products.
Finally, let vi = (viP , viG , viN ) denote a concatenated vector that captures all relevant information for the ith term in the query and let V = (v0, v1, . . . , vn ) denote the vector for the entire search term. We will use this vector as an input to the model to predict the product terms from the search query. We use a convolution neural network (CNN) that consists of three convolution layers with filter sizes of n1 = 7 for the first layer, n2 = 5 for the second layer and n3 = 3 for the third layer. The number of filters are set to 256 in each case. There is no max-pooling layer because we want to keep the filter information for each stride. The output of the last filter is then passed to fully-connected layers with a time-distributed-dense layer as the very last layer for making tag predictions. The intuition behind this model is that the convolution layers are able to capture local information using the parts-of-speech tags of surrounding terms and the number of incoming and outgoing edges for the terms in the vicinity. It is then able to make a decision by combining all three vectors to predict if a term in the query is a product or not. The model is trained using queries across six categories (Electronics, Women’s clothing, Men’s clothing, Kid’s clothing, Furniture, and Home) and the tested using queries from the Baby category. Each query can give zero or more product candidates and we aggregate candidates from all queries to come up with a list of potential products. 4.3
This model is very diferent from the two described earlier. It does
not look at the local term graph but makes a decision using a
word2vec [
ht = ot ⊙ tanh(ct ) ot = σ (Wxoxt + Whoht −1 + Wcoct + bo ) ct = (1 − it ) ⊙ ct −1 + it ⊙ tanh(Wxc xt + Whc ht −1 + bc ) it = σ (Wxi xt + Whi ht −1 + Wci ct −1 + bi ) (1) Let S = (x1, x2, ..., xn ) represent a sentence containing n words where xt represents the word at position t and each word is represented by a d-dimensional vector. We compute the left-context →h−t using a forward LSTM and also a right-context h←−t using a backward LSTM, which reads the same sequence in reverse order. The contexts →h−t and h←−t are computed as shown in equation 1, where σ is the element-wise sigmoid function, ⊙ is the element-wise product, W is the weight matrix and b is the bias. The left and right contexts are then concatenated to represent a word representation ht = [→h−t , h←−t ], which is used by the conditional random field (CRF) for NER tagging.
Lexical features of queries can be quite diferent across categories. So for this method to generalize well, it was important to select the training dataset such that the labeled queries belonged to diferent categories. We chose queries from six categories (Electronics, Women’s clothing, Men’s clothing, Kid’s clothing, Furniture, and Home) for training data and extracted candidate products using queries from the Baby category. 4.4
The token graph method described in section 4.1 is an unsupervised model and so does not require any training data. The other two models are trained using labeled queries from six categories and all three models are tested using the same test set, which are queries from the Baby category. We exclude all broad queries and all queries that are just brands to keep it consistent with the training data. We believe that this is a fair test as it allows us evaluate the model’s performance on a previously unseen category - a task that is essential for automatically creating ontologies.
Each model produces potential product candidates from queries and these candidates are sorted in decreasing order of frequency. We evaluate the top 500 candidates from each model and manually verify if each potential product was actually a product or not. We consider a term to be a product only if it is atomic and sellable on the site. For example, diaper is a product but baby (we don’t sell babies) and diaper cover (not atomic) are not. Table 1 shows the top ten candidates (from the top 500 candidates) from each model along with our manually annotated results denoting if the given entry is a product (P ) or not (N ).
Figure 4 shows a precision @ n graph for all the three models over their top 500 candidates. The LSTM-CRF model produced just over 300 candidates and so its graph is truncated. Both the augmented graph method and the LSTM-CRF method have a higher precision initially and are able to correctly identify products from the query logs. Figure 5 shows a zoomed in view of the first 100 candidates and it can be observed that the augmented graph model is able to predict products more accurately than the LSTM-CRF method. As expected the naive graph method performs the worst in terms of accuracy but can return more products than the LSTM-CRF method. The naive graph method may seem like the worst method but it has one very significant advantage over the other two methods - it is completely unsupervised. This allows it to be used when there is no training data from other categories. We recommend that this method should be used initially and it can pave the way for the other two supervised methods for other categories. 5
In this work we proposed a search-side ontology that can be used for Named Entity Recognition and Classification of Queries. We show that this ontology is better suited for search as compared to supply-side or catalog-side ontologies. We propose three methods to generate Product classes for this ontology. We also compare the three methods and show that the Augmented Graph Method which uses local token information along with parts-of-speech tags performs better than the naive Graph Method and the bidirectional LSTM-CRF method in generating Product classes.
The authors would like to thank Brent Scardapane and Dennis Jordan for their help with the ontology creation process.