Patent ID: 12259895

DETAILED DESCRIPTION

As described above, existing search systems can use learning-to-rank based ranking models. The existing systems can use training data in a machine learning algorithm to produce a ranking model that predicts the relevance of search results. Behavior features constructed based on user feedback towards queries can be important features in ranking models. However, user feedback signals can be sparse. For example, while an electronic catalog system can receive billions of queries every year, only a small fraction of those queries may have sufficient user behavioral signals to build behavior features useful for effective ranking. Many queries may be semantically similar to other queries. However, the corresponding signals for those queries may differ significantly, which can result in unbalanced feature quality for ranking.

Generally described, aspects of the present disclosure are directed to improved search systems and methods that can address sparse behavioral signals. Machine learning can be used to determine queries with historical data that are similar to an input query, which have limited behavioral signals. The machine learning techniques described herein can identify similar queries that would be lexically difficult to determine. In particular, co-acquisitions of items for query pairs can be used to generate a similarity value for the pairs, which can be used as labels during training of machine learning models (which can include a large language model). The systems and methods described herein can advantageously use large language models to capture semantic similarity in language. Moreover, multiple machine learning models can be used during inference such that a subset of similar queries can be determined with a less computationally expensive model and a more computationally expensive model can be used to re-rank the subset of queries. Accordingly, for input queries with limited behavioral data, a system can identify similar queries with behavioral data and their corresponding search results can be presented to a user. The systems and methods described herein can extract similar query behavioral scores into priors used for item search ranking models.

The systems and methods described herein may improve computer performance. As described herein, given 100 million input queries, 100 million historical candidate queries, a cross-encoder/interaction-based model could be called 100M2, which could take 100 million GPU days. With a 10× inference speed and 1,000 GPUs, the predictions could take 10,000 days to finish. When search logs have billions of unique query search result pairs, using a cartesian product directly on all the queries would yield over a trillion query pairs, which can result in out-of-memory issues. Accordingly, given a large set of queries, there can be billions or trillions of query combinations to process, which can pose hardware challenges on data storage, memory (such as out-of-memory issues), and processor executions. Some of the solutions described herein can use faster representation-based model(s) for initial filtering and interaction-based model(s) for re-ranking, which can improve the operation of a computer by allowing the computer processor(s) to make faster predictions. Some of the solutions described herein can employ divide-and-conquer strategies to address the scalability challenges of processing large sets of queries. Therefore, the systems and methods described herein can improve the operation of a computer by efficiently processing large sets of queries in a manner that is scalable for data storage, memory, and processor purposes.

As used herein, the term “interaction-based model” can refer to machine learning models that treat a text pair as a single sequence and encode it through a cross encoder. An interaction-based model can include or be a cross-encoder model. As used herein, the term “representation-based model” can refer to machine learning models that encode a text pair independently. A representation-based model can include or be a bi-encoder model. Machine learning models, such as interaction-based and representation-based models can generate embeddings. As used herein, an “embedding” can refer to a low dimensional vector representation of data, such as, but not limited to, words. An embedding can capture some of the semantics of the input by placing semantically similar inputs closer together in the embedding space. An embedding can be learned and/or reused across models.

As used herein, the term “search result” can refer to an item that is provided in response to a query. An item can refer to a data object that can represent a specific thing that has a number of definable attributes. For example, an item can represent things such as, but not limited to, a physical product, a digital product, and/or an electronic document. The term “item” is used interchangeably to refer to an item itself (e.g., a particular product or particular digital content) and to its description or representation in a computer system or electronic catalog. As will be apparent from the context in which it is used, the term is also sometimes used herein to refer only to the item itself or only to its representation in the computer system. Example items can be music albums, audiobooks, books, movies, television shows, and/or other media products in either an electronic format or physical format. Example items can also be electronic or digital, such as an electronic service or any electronic content provided by a buyer to a seller in which a physical good is not transferred. Users can interact with items. For example, a user can select an item in a user interface to view details about the item. A user can acquire an item. Acquiring an item can refer to consuming an item, such as by watching a movie or listening to a music album.

In the search context, behavioral features can be useful for relevance estimation. Using behavioral features in a learning-to-rank system can be effective because of their ability to encode user behavior. However, behavioral features can take a relatively long time to learn (need many impressions to attain high values) and unlearn (until some other items receive higher values). This phenomenon can adversely affect some items because they have minimal behavioral data. In some existing systems, it takes time for new items to gather enough historical signals to gain higher positions in the ranking. In some existing systems, items, including the highly engaging ones, tend to take a fair amount of time before steadily reaching their highest-ranking position. Amplitude and steepness of ranking climb vary depending on the number of impressions (such as acquisitions and/or user selections) received by an item. Some existing systems can practice tokenization, filtering, and stemming to perform query normalization, which can lead to poorly rewritten queries. Some existing systems can also re-write queries, which can lead to poorly rewritten queries.

The systems and methods described herein may improve information and/or database retrieval technology. The solutions described herein may address the technical deficiencies of learning-to-rank algorithms with respect to the cold-start issues described herein. Machine learning algorithms can be used to identify queries with behavioral data that are similar to an input query and provide search results related to the queries with behavioral data. This approach can advantageously break the zero-feedback loop of existing learning-to-rank models for items that fail to generate user interaction data. The technical solutions described herein can obviate the need for administrators to manually set prediction values that can be a time-consuming, error prone, arbitrary, and/or inefficient process. Moreover, the technical solutions described herein can overcome deficiencies with respect to query normalization and/or query re-writing. Rather, the machine learning and prediction algorithms described herein can enable items with limited behavioral data to be efficiently and/or programmatically ranked, which did not occur in some existing systems. Thus, the systems and methods described herein can improve traditional information retrieval techniques.

Turning toFIG.1, an illustrative network environment100is shown in which a search system104may rank items with minimal behavioral data. The network environment100may include one or more user computing devices102and the search system104. The search system104may include a user interface120, a query service108, a ranking service118, a training service116, an inference service110, an item data storage112, and a training data storage114. The constituents of the network environment100may be in communication with each other either locally or over a network106. While certain constituents of the network environment100are depicted as being in communication with one another, any constituent of the network environment100can communicate with any other constituent of the network environment100; however, not all of these communication lines are depicted inFIG.1. For example, any of the user interface120, the query service108, the ranking service118, the training service116, and the inference service110can communicate directly with each other.

User computing devices102can include, but are not limited to, a laptop or tablet computer, personal computer, personal digital assistant (PDA), hybrid PDA/mobile phone, smart wearable device (such as a smart watch), mobile phone, and/or a smartphone. A user can submit, via the user computing device102, a query122to the search system104, such as by using the user interface120. The query service108can retrieve search results from the item data storage112. In some embodiments, if there are input queries with insufficient behavioral signals, the inference service110can predict similar queries with better behavioral signals and the initial search results can be augmented with the search results for the similar queries. The ranking service118can rank the search results using a ranking model and features that incorporate the behavioral signals from similar queries. The ranked search results124can then be presented on the user interface120. Users, via the user computing device102, can further interact with items via the user interface120as described herein. While not illustrated inFIG.1, in some embodiments, the user interface120may be executed client-side at the user computing device102. For example, an application can execute on the user computing device102that presents the user interface120. As described herein, the training service116can train multiple machine learning models based on data from the training data storage114that are used by the inference service110.

In some embodiments, the item data storage112can be included in and/or interface with an electronic catalog system. The electronic catalog system may include or be in communication with a data store of information about items that may be listed for sale, lease, etc. by an electronic marketplace, sellers, merchants and/or other users. The item information in this data store may be viewable by end users through a browsable or searchable electronic catalog in which each item may be described in association with a network page, such as an item detail page, describing the item. Each item detail page may include, for example, an item image and description, customer ratings, customer and professional reviews, sales rank data, lists of related items, and/or other types of supplemental data that may assist consumers in making informed acquisition decisions. A network page can be provided that enables users to interact with items, such as selecting, acquiring, or consuming items (such as watching or playing a media content item). Users of the system may, in some embodiments, locate specific item detail pages within the electronic catalog by executing search queries, navigating a browse tree, and/or using various other navigation techniques.

The item data storage112and/or the training data storage114may be embodied in hard disk drives, solid state memories, or any other type of non-transitory computer readable storage medium. The item data storage112and/or the training data storage114may also be distributed or partitioned across multiple local and/or remote storage devices. The item data storage112and/or the training data storage114may include a data store. As used herein, a “data store” can refer to any data structure (and/or combinations of multiple data structures) for storing and/or organizing data, including, but not limited to, relational databases (e.g., Oracle databases, MySQL databases, etc.), non-relational databases (e.g., NoSQL databases, etc.), key-value databases, in-memory databases, tables in a database, and/or any other widely used or proprietary format for data storage.

The network106may be any wired network, wireless network, or combination thereof. In addition, the network106may be a personal area network, local area network, wide area network, cable network, satellite network, cellular telephone network, or combination thereof. In addition, the network106may be an over-the-air broadcast network (e.g., for radio or television) or a publicly accessible network of linked networks, possibly operated by various distinct parties, such as the Internet. In some embodiments, the network106may be a private or semi-private network, such as a corporate or university intranet. The network106may include one or more wireless networks, such as a Global System for Mobile Communications (GSM) network, a Code Division Multiple Access (CDMA) network, a Long-Term Evolution (LTE) network, or any other type of wireless network. The network106can use protocols and components for communicating via the Internet or any of the other aforementioned types of networks, such as HTTP, TCP/IP, and/or UDP/IP.

The user computing devices102and/or the search system104may each be embodied in a plurality of devices. Each of the user computing devices102and/or the search system104may include a network interface, memory, hardware processor, and non-transitory computer-readable medium drive, all of which may communicate with each other by way of a communication bus. The network interface may provide connectivity over the network106and/or other networks or computer systems. The hardware processor may communicate to and from memory containing program (a.k.a., computer-executable) instructions that the hardware processor executes in order to operate the user computing devices102and/or the search system104. The memory generally includes RAM, ROM, and/or other persistent and/or auxiliary non-transitory computer readable storage media.

Additionally, in some embodiments, the search system104or components thereof are implemented by one or more virtual machines implemented in a hosted computing environment. The hosted computing environment may include one or more rapidly provisioned and/or released computing resources. The computing resources may include hardware computing, networking and/or storage devices configured with specifically configured computer executable instructions. A hosted computing environment may also be referred to as a “serverless,” “cloud,” or “distributed” computing environment.

FIG.2is a schematic diagram of an illustrative general architecture of a computing system201for implementing a computing device within the search system104referenced in the environment100inFIG.1. The computing system201includes an arrangement of computer hardware and software components that may be used to execute the training application222and/or the inference application224. The general architecture ofFIG.2can be used to implement other devices described herein, such as the user computing device102referenced inFIG.1. The computing system201may include more (or fewer) components than those shown inFIG.2. Further, other computing systems described herein may include similar implementation arrangements of computer hardware and/or software components.

The computing system201for implementing a device within the search system104may include a hardware processor202, a network interface204, a non-transitory computer-readable medium drive206, and an input/output device interface208, all of which may communicate with one another by way of a communication bus. As illustrated, the computing system201is associated with, or in communication with, an optional display218and an optional input device220. The network interface204may provide the computing system201with connectivity to one or more networks or computing systems. The hardware processor202may thus receive information and instructions from other computing systems or services via the network106. The hardware processor202may also communicate to and from memory210and further provide output information for an optional display218via the input/output device interface208. The input/output device interface208may accept input from the optional input device220, such as a keyboard, mouse, digital pen, and/or touch screen. The input/output device interface208may also output audio data to speakers or headphones (not shown).

The memory210may contain specifically configured computer program instructions that the hardware processor202executes in order to implement one or more embodiments of a device within the search system104. The memory210generally includes RAM, ROM and/or other persistent or non-transitory computer-readable storage media. The memory210may store an operating system214that provides computer program instructions for use by the hardware processor202in the general administration and operation of the device within the search system104.

The memory210may include a training application222and/or an inference application224that may be executed by the hardware processor202. In some embodiments, the training application222and/or the inference application224may implement various aspects of the present disclosure. In some embodiments, item-related data (such as behavioral data) can be processed; the training application222can train and/or retrain machine learning model(s); and the inference application224can identify queries similar to an input query.

As described herein, labels can be used to train machine learning models to predict query similarity. For an input query, qi, and a candidate query, cij, similarity can be denoted as yij. The similarity value, yij, can have a range, such as greater than 0 to 1. The similarity value can be approximated by considering co-acquisitions between the input query and the candidate query. In some embodiments, training data can be denoted as shown in Table 1 below where Ciis the set of candidate queries that are close to the input query, qi.

TABLE 1T = {(qi, cij, yij)}iϵ{1,2, ... ,|Ci|}N

In some embodiments, the similarity value, yij, can be calculated based on two types of similarity for queries, such as, an (i) overlap similarity, OS, and a jaccard similarity, JS. Overlap similarity, OS, can also be referred to as an overlap coefficient and/or a similarity measure. Overlap similarity, OS, can measure the overlap between two sets. Overlap similarity, OS, can be the size of the intersection between the two sets divided by the smaller of the size of the two sets, as shown in Table 2. In the equation in Table 2, N denotes the unique acquired items from the query.

TABLE 2OS=❘"\[LeftBracketingBar]"N⁡(qi)⋂N⁡(ci⁢j)❘"\[RightBracketingBar]"min⁡(❘"\[LeftBracketingBar]"N⁡(qi)❘"\[RightBracketingBar]",❘"\[LeftBracketingBar]"N⁡(ci⁢j)❘"\[RightBracketingBar]")

Jaccard similarity, JS, can also be referred to as a Jaccard similarity coefficient and/or Jaccard index. Jaccard similarity, JS, can gauge the similarity and diversity of sets. Jaccard similarity, JS, can be the size of the intersection divided by the size of the union of the sets, as shown in Table 3. The use of Jaccard similarity, JS, can advantageously prevent popular queries from dominating every query's candidate query list. A popular query can be a query that has many acquisitions of different items. For example, a “running shoes” query can be a popular query that is associated with many different item acquisitions.

TABLE 3JS=❘"\[LeftBracketingBar]"N⁡(qi)⋂N⁡(cij)❘"\[RightBracketingBar]"❘"\[LeftBracketingBar]"N⁡(qi)⋃N⁡(cij)❘"\[RightBracketingBar]"

A combination of overlap similarity, OS, and Jaccard similarity, JS, can be used for training labels. In some embodiments, the similarity value of two queries can be based on multiplying overlap similarity, OS, and Jaccard similarity, JS, as shown in Table 4. The similarity value, yij, can be close to 1 when the input query, qi, and the candidate query, cij, are associated with a sufficient threshold of co-acquired items relative to other candidate queries. The labels (the similarity values) can be used to create a model to fit on the input query, the candidate query, and the similarity value (qi, cij, yij) to score the similarity of the queries.

TABLE 4QuerySimilarity = OS(qi, cij) * JS(qi, cij)

FIG.3depicts a methodology300for determining a similarity score between queries. As described herein, a similarity score between queries can be used to train machine learning models to determine similar queries. The methodology can include three components: (1) input, (2) encoding layer(s), and (3) similarity calculation layer(s). The input can include an input query302and a candidate query304. In some embodiments, the input and candidate queries302,304can be selected to meet certain criteria, such as, but not limited to, the queries302,304being associated with the multiple instances of the same acquired item within a time period (such as three different common acquisitions within a year). Using certain criteria to select the query pairs302,304can advantageously prevent weak query pairs from being generated.

The training service116can feed the input and candidate queries302,304to the pre-trained model(s)306. The pre-trained model(s) can be or include large language models. Depending on the embodiment, the training service116can feed the input and candidate queries302,304differently to the pre-trained model(s)306. If the pre-trained model(s)306are or include a bi-encoder model, the training service116can feed the input and candidate queries302,304separately to the pre-trained model(s)306, which output the two separate embeddings308A,308B. If the pre-trained model(s)306are or include a cross-encoder model, the training service116can concatenate the input and candidate queries302,304(such as by using special tokens) and feed the concatenated input to the pre-trained model(s). For example, the training service116can generate input with the following format shown in Table 5, where <CLS> is the classification token and <SEP> separates sentences.

TABLE 5<CLS> INPUT QUERY <SEP> CANDIDATE QUERY <SEP>

The training service116can receive the embeddings308A,308B from the pre-trained model(s)306. The training service116can apply a similarity calculation310to the embeddings308A,308B. The similarity calculation310can output the similarity score312. Depending on the embodiment, a different similarity calculation310can be performed. The similarity calculation310can include a cosine similarity function, a multi-layer perceptron, or a combination including the cosine similarity function and the multi-layer perceptron. For example, the embeddings can (i) feed into the multi-layer perceptron and a cosine similarity function and (ii) the output of the cosine similarity function can also feed into the same multi-layer perceptron.

In embodiments where the pre-trained model(s)306are or include a bi-encoder model, the bi-encoder model can be a class of models referred to as a representation-based model, such as, but not limited to a neural network encoder. The representation-based model can receive a query as input and output a feature embedding vector, which can be performed on the input query302and the candidate query304. The training service116can feed the generated embeddings of the two queries into a dot product and/or perceptron to calculate the similarity score312. In some embodiments, bi-encoder/representation-based models can have low inference costs that when deployed advantageously have low latency performance.

In embodiments where the pre-trained model(s)306are or include a cross-encoder model, the pre-trained model(s)306and the similarity calculation310can be an interaction-based model. A cross-encoder model can have multiple inputs and can advantageously allow informational interactions at a relatively early stage by leveraging their attention heads to exploit inter-query interactions. In some embodiments, the training service116can feed two connected feature embeddings into a multi-layer perceptron and/or leverage an attention mechanism between the two input queries to calculate the similarity score312.

FIGS.4A-4Bdepict illustrative methodology for generating training data that includes query pairs and similarity values.FIG.4Adepicts a methodology400where item-related data402is transformed into the query-pairs data410. As shown, the item-related data402can include the input queries404A,404B, overlap history406A,406B, and candidate queries408A,408B. In particular, the first input query404A is “full size bed sheet” and the second input query404B is “cookie sheet pan”. The overlap history406A,406B shown as lines can indicate that (i) the first input query404A has common item acquisitions with three candidate queries and (ii) the second input query404B has different, common item acquisitions with three other candidate queries. As shown, the thicker line for the first overlap history406A between the first input query404A (here “full size bed sheet”) and a first candidate query408A (here “sheet full size”) can represent that there are relatively more common acquisitions than the thinner line for the second overlap history406B between the second input query404B (here “cookie sheet pan”) and a second candidate query (here “pan sheet holder”). The item-related data402shown inFIG.4Acan illustrate how common lexical queries (such as the queries with the word “sheet” shown in underline) can have different similarities with other queries that can be determined from the common acquisitions between queries (which can distinguish between bed sheet type queries and sheet pan type queries).

The training service116can generate the query-pairs data410from the item-related data402. As shown, the training service116can generate positive pairs and negative pairs from the item-related data402. The training service116can generate positive pairs where queries that have common acquisitions. The training service116can generate negative pairs from randomly or pseudo randomly pairing queries that do not share a common acquisition history. The training service116can generate a first similarity value (here 1.0) for a first query pair412A (here “full size bed sheet” and “sheet full size”). Similarly, the training service116can generate a second similarity value (here 0.4) for a second query pair412B (here “cookie sheet pan” and “pan sheet holder”). The first similarity value (here 1.0) can be higher than the second similarity value (here 0.4) at least because the first query pair412A can have relatively more common acquisitions than the second query pair412B. As shown, a negative pair414(here “full size bed sheet” and “sheet pan”) can be assigned a zero similarity value since the first input query404A and a particular candidate query408C do not have any common acquisitions.

FIG.4Bdepicts training data420in a table format that includes query pairs and similarity values. A first data entry422in the training data420includes a first input query (here “goya lady fingers”) and a first candidate query (here “lady fingers for tiramisu”). The first data entry422further includes item-related data, such as, the size of the intersection between the sets of acquired items between the first input query and the first candidate query (here 9), the size of the union of the sets of acquired items between the first input query and the first candidate query (here 42), and the smaller of the size of the sets of acquired items between the first input query and the first candidate query (here 12). The training service116can generate similarity values (such as the Jaccard similarity, overlap similarity, and a similarity value) from the item-related data. In the first data entry422, training service116can calculate: the Jaccard similarity (here 0.214) from the size of the intersection (here 9) divided by the size of the union of the sets (here 42); the overlap similarity (here 0.75) from the size of the intersection between the two sets (here 9) divided by the smaller of the size of the two sets (here 12); and the similarity value (here 0.161) by multiplying the Jaccard similarity (here 0.214) and the overlap similarity (here 0.75).

The training data420can represent candidate queries that have similar acquisition history with an input query, here “goya lady fingers.” Lady finger is a type of sponge cake biscuit and Goya® is a brand name. In the training data, the top-ranked candidate queries can include the “lady fingers for tiramisu” candidate query. It is not straightforward to automatically determine that “tiramisu” queries are similar to a “goya lady finger” query at a lexical level. However, the behavioral signals in the item-related data can indicate that queries share similar acquired items, which can be used to teach models to learn the semantic level similarity.

As described herein, the training service116can use the training data to train one or more machine learning models, such as, but not limited to, representation-based models and/or interaction-based models. The training service116can use the similarity values, yij, as training labels. The similarity value, yij, can have a range, such as greater than 0 to 1, when the input query, qi, and the candidate query, cij, have co-acquired items. The similarity value, yij, can be assigned a 0 value when the input query, qi, and the candidate query, cij, have no co-acquired items. The training service116can generate negative pairs (qi, cij, 0) where there were no co-acquired items for the input query, qi, and the candidate query, cij, and mix them with positive pairs (qi, cij, yij) to train a model on the labels. During training, the training service116can use a loss function, such as, but not limited to, binary cross entropy (BCE) loss function and/or mean square error (MSE) loss function. A BCE loss function is shown in Table 6 below and a MSE loss function is shown below in Table 7. In the formulas of Tables 6 and 7, y is the label and p(yij) can be the predicted probability for the label being 1 for all N labels.

TABLE 6LBCE=-1N⁢∑i=1Nyi⁢j⁢log⁡(p⁡(yi⁢j))+(1-yi⁢j)·log⁡(1-p⁡(yi⁢j))

TABLE 7LBCE=1N⁢∑i=1N(yi⁢j-p⁡(yi⁢j))2

FIG.5depicts a methodology500for predicting similar queries based on an input query502. The methodology500can include a representation-based model504, a nearest-neighbor search model508, and an interaction-based model512. At the first stage, a representation-based model504can be selected based on performance. As described herein, different pre-trained models (such as different LLMs) can be used as the representation-based model504, evaluation metrics can be generated for each representation-based model, and a particular representation-based model504can be selected for use based on the evaluation metrics. Similarly, as described herein, different pre-trained models (such as different LLMs) can be used as the interaction-based model512, evaluation metrics can be generated for each interaction-based model, and a particular interaction-based model512can be selected for use based on the evaluation metrics. In some embodiments, queries with sufficient behavioral signals are processed by representation-based model504to generate embeddings and the embeddings are added to the nearest-neighbor search model508.

In some embodiments, the nearest-neighbor search model508can be or include a graph-based, nearest-neighbor search model508. The nearest-neighbor search model508can make use of, but is not limited to, a PECOS Approximated Nearest Neighbor (ANN) search module that implements the Hierarchical Navigable Small World Graphs (HNSW) algorithm. The nearest-neighbor search model508can enable fast retrieval for large-scale vector similarity searching. The nearest-neighbor search model508can index the embeddings.

The inference service110can receive an input query502. In the first stage, the representation-based model504can process the input query502to generate an embedding506. The nearest-neighbor search model508can process the embedding506for the input query502to identify the nearest-neighbor embeddings to the embedding for the input query502. As described herein, closeness of embeddings can be determined based on a cosine similarity, a multi-layer perceptron, or a combination including the cosine similarity and the multi-layer perceptron calculation. The first subset of queries510corresponding to the nearest-neighbor embeddings can be provided to the second stage for re-ranking. In the second stage, the interaction-based model512can process each query from the first subset of queries510to predict similarity to the input query502. The inference service110can select a second subset of queries514that satisfies a threshold. In some embodiments, the inference service110can select those queries with a similarity score that satisfy a threshold. Additionally or alternatively, the inference service110can select a predetermined number of queries with a highest similarity score.

In some cases, cross-encoder/interaction-based models can outperform bi-encoder/representation-based models. However, the computational cost to execute cross-encoder/interaction-based models can be higher than the computational cost for bi-encoder/representation-based models. For example, given 100 million input queries, 100 million historical candidate queries, a cross-encoder/interaction-based model could be called 100M2, which could take 100 million GPU days. With a 10× inference speed and 1,000 GPUs, the predictions could take 10,000 days to finish. Accordingly, the architecture ofFIG.5, which uses faster representation-based model(s) for initial filtering and interaction-based model(s) for re-ranking can improve the operation of a computer by allowing the computer processor(s) to make faster predictions.

FIG.6includes a flow diagram depicting a method600implemented by the search system104for machine learned searching and ranking. As described herein, the search system104may be implemented with the computing system201. In some embodiments, the computing system201may include the training application222and/or the inference application224, each of which may implement aspects of the method600. Some aspects of the method600may be implemented by the services of the search system104, such as the query service108, the ranking service118, the training service116, and/or the inference service110. In some embodiments, the method600can be applied for inferencing and/or training purposes. Moreover, some aspects of the method600may be described above with respect toFIGS.3,4A,4B,5.

Beginning at block602, query and behavioral data can be received. The search system104can store queries received from user computing devices102. Each query can include text data. The search system104can store records of the search results for the queries and behavioral data associated with the queries. Behavioral data can include, but is not limited to, acquisitions data (such a record of acquired items associated with a query), user selections of a search result, or any other user interaction with a search result, which can be referred to as an impression.

At block604, similarity values from the query and behavioral data can be calculated. The training service116can calculate similarity values from the query and behavioral data. The training service116can determine a quantity of co-acquired items associated with a first query and a second query, which can be referred to as a query pair. The training service116can determine a similarity value from the quantity of co-acquired items associated with the query pair. As described herein, the training service116can calculate an overlap similarity and a jaccard similarity using the quantity of co-acquired items. The training service116can determine a similarity value by combining the overlap similarity and the jaccard similarity. The training service116can determine a lack of co-acquired items for other query pairs. Additional details regarding calculating a similarity value are described herein, such as with respect toFIG.4Band Table 4. In some embodiments, the training service116can calculate similarity values for queries that have sufficient behavioral data. The training service116can filter the queries to those that have at least a predetermined number (such as three) of co-acquired items within a timer period (such as a year). Filtering the queries can advantageously prevent weak query pairs from being generated in the training data.

As described herein, the training service116can calculate an overlap similarity. The training service116can determine a quantity of acquired items associated with the first query and a quantity of acquired items associated with the second query. The training service116can identify a smaller quantity of acquired items from the quantities of acquired items for the first and second queries. To calculate the overlap similarity, the training service116can divide the quantity of co-acquired items by the smaller quantity of acquired items. Additional details regarding calculating overlap similarity are described herein, such as with respect toFIG.4Band Table 2.

As described herein, the training service116can calculate a jaccard similarity. The training service116can determine a first set of acquired items associated with the first query and a second set of acquired items associated with the second query. The training service116can determine a size of a union set between the first set and the second set. To calculate the jaccard similarity, the training service116can divide the quantity of co-acquired items by the size of the union set. Additional details regarding calculating jaccard similarity are described herein, such as with respect toFIG.4Band Table 3.

At block606, training data and labels can be generated from the similarity values. The training service116can generate training data that includes the queries and the similarity values as labels. The training service116can add query pairs and the similarity value for the query pair to the training data. The training service116can generate training data that includes a query pair and a similarity value as a label for the query pair. The added query pairs can be positive query pairs in that the queries have co-acquired items associated with them. The similarity value for query pairs with co-acquired items can be a positive label. The training service116can add query pairs that lack co-acquired items to the training data with negative labels. A negative label can include, but is not limited to, a zero value. The training service116can randomly or pseudo-randomly select pairs of queries without co-acquired items between them and mix them with the positive query pairs in the training data. The training service116can assign a zero value as a label for the negative query pairs in the training data.

At block608, one or more machine learning models can be trained. The training service116can train the one or more machine learning models using supervised and/or semi-supervised machine learning. As described herein, the one or more machine learning models can be representation-based models and/or interaction-based models. The one or more machine learning models can also be or include a pre-trained model and/or a large language model. The representation-based models and/or interaction-based model can be or include a large language model. Large language models can include, but are not limited to, a bidirectional encoder representations from transformers (BERT) model, a sentence BERT model, or a generative pre-trained transformer (GPT) model. The training service116can train a pre-trained model with the training data, which outputs a representation-based model and/or an interaction-based model. As described herein, in the case of a representation-based model, the representation-based model can be trained to receive an input query and output a first embedding. The representation-based model can receive a candidate query and output a second embedding. The training service116can generate a similarity score from the first and second embeddings. As described herein, in the case of an interaction-based model, the interaction-based model can be trained to receive an input query and a candidate query and output a similarity score. The training service116can use the labels, a loss function, and backpropagation to update the machine learning model(s) during training, which causes weights in the machine learning model(s) to update. As described herein, the training service116can use loss functions such as, but not limited to, a binary cross entropy loss function and/or a mean square error loss function.

In some embodiments, the performance of a bi-encoder and/or representation-based model can be improved via transfer learning. The training service116can train a cross-encoder model with the training data. As described herein, a cross-encoder model can have better performance than a bi-encoder model, but at a greater computational cost. Thus, the training service116can use the output from a cross-encoder model to train a bi-encoder and/or a representation-based model. The training service116can receive output from the cross-encoder model where the output includes similarity scores. The training service116can a pre-trained model with the training data based on the output, which can output a representation-based model.

In some embodiments, the pre-trained model can be trained specifically for an organization. For example, the pre-trained model can be a large language model that is trained on the e-commerce data from an organization. In some cases, the custom pre-trained models can outperform third-party pre-trained models. The training service116can train a large language model using training data, such as organization specific training data. The training service116can determine a quantity of co-acquired items associated with a query pair and determine a similarity value from the quantity of co-acquired items associated with the query pair. The training service116can generate training data that includes (i) the query pair and (ii) the similarity value as a label for the query pair. Additional types of training data are described herein, such as with respect to the previous block606. The training service116can retrain the large language model using the generated training data, which outputs the representation-based and/or the interaction-based model.

At block610, an input query can be received. The user interface120can receive an input query. In some embodiments, a query service108can retrieve search results from the item data storage112based on the input query. As described herein, if the input query is associated with insufficient behavioral signals, the inference service110can predict similar queries with better behavioral signals.

At block612, a representation-based model can be executed. The inference service110can execute a representation-based model. The inference service110can execute a representation-based model wherein the representation-based model receives the input query and outputs a first embedding. As described herein, the representation-based model can be trained using the similarity values as labels.

At block614, one or more similar embeddings can be identified. The inference service110can identify a second embedding associated with a candidate query similar to the first embedding associated with the input query. The inference service110can determine similarity between embeddings using a cosine similarity calculation and/or a multi-layer perceptron. In some embodiments, the inference service110can identify similar embeddings to the first embedding using a nearest-neighbor search model. The inference service110can determine a candidate query associated with the second embedding. Additional details regarding identifying similar embeddings are described herein, such as with respect toFIG.5.

In some embodiments, the inference service110can identify an embedding similar to the embedding derived from the input query using a representation-based model. The inference service110can execute a representation-based model where the representation-based model receives the candidate query and outputs a second embedding. The inference service110can calculate a similarity score from the first embedding (derived with the input query) and the second embedding (derived from the candidate query). The inference service110can determine that the similarity score satisfies a threshold. In some embodiments, the threshold can be set higher or lower depending on the performance of the model, such as the representation-based model. If the accuracy of the representation-based model is higher, then the threshold can be set lower and vice versa.

The inference service110can calculate the similarity score using a cosine similarity. The inference service110can apply a cosine similarity function to the first embedding and the second embedding. A cosine similarity can be a measure of similarity between two non-zero vectors defined in an inner product space. Cosine similarity can be the cosine of the angle between the vectors, which can be calculated via the dot product of the vectors divided by the product of their lengths. The distance or cosine similarity between two vectors can measure whether the two queries are semantically related.

The inference service110can calculate the similarity score using a multilayer perceptron. The inference service110can apply the first embedding and the second embedding to a multilayer perceptron where the multilayer perceptron outputs the similarity score. A multilayer perceptron can refer to a fully connected feedforward neural network. A multilayer perceptron can include an input layer, a hidden layer, and an output layer. Except for the input nodes, each node can be a neuron that uses a nonlinear activation function. The multilayer perceptron can use backpropagation or reverse mode of automatic differentiation for training.

The inference service110can calculate the similarity score using a cosine similarity and a multilayer perceptron. The inference service110can apply a cosine similarity function to the first embedding and the second embedding. The cosine similarity function can output a cosine similarity value. The inference service110can apply the first embedding, the second embedding, and the cosine similarity value to a multilayer perceptron where the multilayer perceptron outputs the similarity score.

In some embodiments, the inference service110can identify an embedding similar to the embedding derived from the input query using a nearest-neighbor search model. The inference service110can provide, to a nearest-neighbor search model, the first embedding as input, wherein the nearest-neighbor search model outputs the second embedding. As described herein, the nearest-neighbor search model508can make use of, but is not limited to, a PECOS ANN search module that implements the HNSW algorithm. Additional details regarding using a nearest-neighbor search mode are described herein, such as with respect toFIG.5.

At block616, an interaction-based model can be executed. The inference service110can execute an interaction-based model. The inference service110can execute an interaction-based model where the interaction-based model receives (i) the input query and (ii) the candidate query and outputs a similarity score. Additional details regarding executing machine learning models, such as an interaction-based model, are described herein, such as with respect toFIG.5.

At block618, it can be determined whether the similarity score satisfies a threshold. The inference service110can determine whether the similarity score satisfies a threshold, such as by selecting a predetermined number of candidate queries with the highest similarity scores. Additionally or alternatively, the inference service110can determine whether the similarity score is above a threshold value. As described herein, the threshold can be set higher or lower depending on the performance of the model, such as the interaction-based model. If the accuracy of the interaction-based model is higher, then the threshold can be set lower and vice versa. If the similarity score satisfies the threshold, the method600proceeds to block620to execute a ranking model. Otherwise, the method600can end since the candidate query is not similar enough to the input query. In some embodiments, a block (not illustrated) similar to block618can be performed after the previous block614for identifying similar embeddings. For example, the inference service110can filter out candidate queries with lower similarity scores before they are processed by the block616for executing an interaction-based model.

At block620, a ranking model can be executed. The query service108can retrieve search results associated with the one or more candidate queries. The ranking service118can execute a ranking model. The ranking service118can generate ranking features for the input query and a search result using a behavioral signal for the candidate query. The ranking service118can advantageously improve search ranking by augmenting queries where behavioral signals are sparse with prior scores. The ranking service118can execute a ranking model where the ranking model receives the ranking features and outputs a predicted ranking. In some embodiments, the ranking model can receive two ranking features and output a predicted ranking for two search results. The ranking service118can apply an algorithm ranking pairs of search results to determine a ranking for a set of search results. In other embodiments, the ranking model can receive a list ranking features and output a predicted ranking for the list of search results. In some embodiments, the ranking model can be or include a tree-based ranking model.

The ranking service118can generate ranking features based on multiple candidate queries. As described herein, the inference service110can identify multiple candidate queries similar to the input query. The ranking service118can generate the ranking feature for the input query and the search result based on the multiple candidate queries. For each candidate query from the multiple candidate queries, the ranking service118can combine a behavioral signal for the candidate query and the first search result. As described herein, for a given input query, q, the method600can find the query's similar queries, Cq={c1, . . . , cm}, based on similar behavioral signals. The ranking service118can generate a prior for the input query using behavioral signals from the similar queries. For the input query, q, and a related search result, r, H(q,r) is used to represent the behavioral signal score. The equation in Table 8 below represents how the ranking service118can combine a behavioral signal for each candidate query for a prior for the input query and the search result, Prior(q,r).

TABLE 8Prior⁢(q,r)=1❘"\[LeftBracketingBar]"Cq❘"\[RightBracketingBar]"⁢∑i∈[1,m]H⁡(ci,r)

The ranking service118can generate the ranking feature by combining the prior, Prior(q,r), with the behavioral signal score, H(q,r). The equation in Table 9 below represents how the ranking service118can calculate the ranking feature, F(q,p).

TABLE 9F(q, p) = α · H(q, r) + (1 − α) · Prior(q, r) · β

In the equation of Table 9, a can be defined in Table 10 below and the ranking service118can compute a from query-result impressions. The greater the query-result impressions, the higher a can be in the equation of Table 9, which can be used to balance the weight between observed behavioral signals and prior scores. In the equation of Table 10, Iq,rcan denote the number of impressions result, r, for the input query, q, and γ can be a constant to cap very large numbers. In the equation of Table 9, R can be the confidence rate to further adjust the weight of the prior.

TABLE 10α=tanh[min⁡(γ,Iq,r)min⁡(γ,maxr(Iq,r))]

At block622, search results can be provided. The ranking service118can provide the search results. In some embodiments, the user interface120can cause presentation of the search result according to the predicted ranking. The user interface120can be a graphical user interface.

While the systems and methods described herein are discussed on the context of providing search results they can also be applied to other contexts. Additional contexts, can include, but are not limited to, inline search recommendation, recommending related items to users, and/or adding links to a knowledge graph. Also, the systems and methods described herein can also natively support other languages. For example, the machine learning algorithms described herein can process input queries and/or identify similar queries in multiple languages and/or languages other than English.

Not necessarily all objects or advantages may be achieved in accordance with any particular embodiment described herein. Thus, certain embodiments may be configured to operate in a manner that achieves or optimizes one advantage or group of advantages as taught herein without necessarily achieving other objects or advantages as may be taught or suggested herein.

All of the processes described herein may be embodied in, and fully automated via, software code modules executed by a computing system that includes one or more computers or processors. The code modules may be stored in any type of non-transitory computer-readable medium or other computer storage device. Some or all the methods may be embodied in specialized computer hardware.

Many other variations than those described herein will be apparent from this disclosure. For example, depending on the embodiment, certain acts, events, or functions of any of the algorithms described herein can be performed in a different sequence, can be added, merged, or left out altogether (e.g., not all described acts or events are necessary for the practice of the algorithms). Moreover, in certain embodiments, acts or events can be performed concurrently, e.g., through multi-threaded processing, interrupt processing, or multiple processors or processor cores or on other parallel architectures, rather than sequentially. In addition, different tasks or processes can be performed by different machines and/or computing systems that can function together.

The various illustrative logical blocks and modules described in connection with the embodiments disclosed herein can be implemented or performed by a machine, such as a processing unit or processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A processor can be a microprocessor, but in the alternative, the processor can be a controller, microcontroller, or state machine, combinations of the same, or the like. A processor can include electrical circuitry configured to process computer-executable instructions. In another embodiment, a processor includes an FPGA or other programmable device that performs logic operations without processing computer-executable instructions. A processor can also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration. Although described herein primarily with respect to digital technology, a processor may also include primarily analog components. For example, some or all of the signal processing algorithms described herein may be implemented in analog circuitry or mixed analog and digital circuitry. A computing environment can include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a device controller, or a computational engine within an appliance, to name a few.

Conditional language such as, among others, “can,” “could,” “might” or “may,” unless specifically stated otherwise, are otherwise understood within the context as used in general to convey that certain embodiments include, while other embodiments do not include, certain features, and/or elements. Thus, such conditional language is not generally intended to imply that features, and/or elements are in any way required for one or more embodiments or that one or more embodiments necessarily include logic for deciding, with or without user input or prompting, whether these features, and/or elements are included or are to be performed in any particular embodiment. The terms “comprising,” “including,” “having,” and the like are synonymous and are used inclusively, in an open-ended fashion, and do not exclude additional elements, features, acts, operations, and so forth. Further, the term “each,” as used herein, in addition to having its ordinary meaning, can mean any subset of a set of elements to which the term “each” is applied. The term “substantially” when used in conjunction with the term “real time” can refer to speeds in which no or little delay occurs.

Disjunctive language such as the phrase “at least one of X, Y, or Z,” unless specifically stated otherwise, is otherwise understood with the context as used in general to present that an item, term, etc., may be either X, Y, or Z, or any combination thereof (e.g., X, Y, and/or Z). Thus, such disjunctive language is not generally intended to, and should not, imply that certain embodiments require at least one of X, at least one of Y, or at least one of Z to each be present.

Any process descriptions, elements or blocks in the flow diagrams described herein and/or depicted in the attached figures should be understood as potentially representing modules, segments, or portions of code which include one or more executable instructions for implementing specific logical functions or elements in the process. Alternate implementations are included within the scope of the embodiments described herein in which elements or functions may be deleted, executed out of order from that shown, or discussed, including substantially concurrently or in reverse order, depending on the functionality involved as would be understood by those skilled in the art.

Unless otherwise explicitly stated, articles such as “a” or “an” should generally be interpreted to include one or more described items. Accordingly, phrases such as “a device configured to” are intended to include one or more recited devices. Such one or more recited devices can also be collectively configured to carry out the stated recitations. For example, “a processor configured to carry out recitations A, B and C” can include a first processor configured to carry out recitation A working in conjunction with a second processor configured to carry out recitations B and C.

It should be emphasized that many variations and modifications may be made to the above-described embodiments, the elements of which are to be understood as being among other acceptable examples. All such modifications and variations are intended to be included herein within the scope of this disclosure and protected by the following claims.