Patent ID: 12243087

To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the drawings. It is contemplated that elements and features of one embodiment may be beneficially incorporated in other embodiments without further recitation.

DETAILED DESCRIPTION

Aspects of the present disclosure provide apparatuses, methods, processing systems, and computer-readable mediums for efficiently processing a vast data set (such as that of an e-commerce grocery platform) to recommend substitutes that are less likely to be rejected.

A retailer wishing to build a substitute list for each item that it sells requires a significant undertaking. A data set covers each item described using a number of attributes including at least one of identifier, name, description, category name, brand, price, volume, weight, back-of-pack tags or item tags (i.e. key item characteristics such as “vegan”, “kosher”, “alcoholic”, “flammable”), customer revenue segment (e.g. items in same revenue segment), sales trend, seasonality, or rejection rate. With an increasing number of items and customers, the data set grows in size, which complicates analysis. A basic analysis of this data set may allow an acceptable substitute to be determined. However, a detailed analysis allows the “best” substitute to be determined in that the probability of rejection by a customer is minimized. A system to automatically process this immense data set to reduce the rejection of substitutes is desirable.

FIG.1shows a high level diagram100of how such a data set can be processed to reduce the rejection of substitutes. In block110, an item to be substituted is identified. This may be the result of the unavailability of the item, which may be a grocery item ordered via an e-commerce system. Although this is one example use, it would be appreciated that an “item to be substituted” includes an item for which a substitute item is to be identified (i.e. should an item become unavailable, a substitute can be identified; in other words, the item itself may be currently available, but a substitute nonetheless has been identified). In various examples described herein, an “item to be substituted” may be referred to as a “target item.” At least one item similar to the item to be substituted can be determined by block120. For example, if the item to be substituted has pizza in its name, all pizzas (irrespective of type) should be identified by block120. It should be noted that each item may be denoted using a respective identifier. The output of block110is a list of pairings, where each pair includes the item to be substituted and a respective one of the similar items. It can be appreciated that block110provides an initial data filtering step.

These pairings are evaluated by block130to limit the pairings to a number of acceptable pairings. As part of this process, block130receives input from block140, which can identify a primary category for the item to be substituted and each of the similar items. A primary category is the single most relevant category for each item (for example sausages may be listed under the categories of BBQ, Offer 2-4-1 (i.e. 2 items for the price of 1), Meat & Poultry etc., but the most relevant primary category is sausages). The inventors have found that knowledge of the primary category of each item can help effectively limit the pairings to acceptable pairings. In other words, acceptable pairings are those which define an item to be substituted and a “good” substitute. When the acceptable pairings (or potential list of substitutes) have been determined, they can be ranked using the predicted rejection rate (i.e. how likely it is that a chosen substitute item for the item to be substituted, is rejected by a customer) determined by block150.

The inventors have found that the processing carried out by blocks110,120,130,140and150can automatically execute a complex analysis of a large data set to determine the “best” substitute for a given item. Each of the blocks110,120,130,140, and150is implemented using a respective machine learning model, each of which is explained in more detail below.

FIG.2shows a method200carried out by the processing blocks ofFIG.1. In step210, an item to be substituted (e.g., “a target item”) is identified. In step220, using a first trained model, at least one similar item to the item to be substituted, is identified. In step230, using a second trained model, a primary category of the item to be substituted and the one or more similar items, is identified. In step240, using a third trained model, potential substitutes for the item to be substituted based on the at least one similar item, the primary category of the item to be substituted, and the primary category of the at least one similar item, are identified. In step250, using a fourth trained model, the potential substitutes based on a rejection probability of each of the potential substitutes, are ranked. In step260, the ranked potential substitutes are output.

FIG.3shows a processing diagram300of block120in detail. Block310may receive data of the items including at least one of names of the plurality of items, descriptions of the plurality of items, or categories of the plurality of item. The plurality of items, descriptions of the plurality of items, or categories of the plurality of items may be processed by block320, which can be a Natural Language Processing, NLP, such as a Latent Dirichlet Allocation, LDA, process to determine the number of topics to which a given item belongs. The more topics a pair of products share in common, the more likely they are to be similar. For example, a vegetarian pizza will have more topics (e.g. name, crust type and base size) common with a meat pizza, compared to a vegetarian lasagna. It will be appreciated that the LDA model can be developed using supervised or unsupervised machine learning. An appropriate training data set ensures that a good range of topics are identified.

FIG.4shows a processing diagram400of block140in detail. Block410may receive data of the items including at least one of the item to be substituted and each similar item (i.e. the pairings produced by block110), a name of the item to be substituted and a name of each similar item, or a description of the item to be substituted and a description of each similar item.

Block420may compute a similarity metric, such as the Jaccard index or Jaccard similarity index between the categories of the items. To compute the similarity, each item in the pairings may be grouped according to the each of the categories to which it is assigned. If an item in each category is similar to several other items in a given category, it will score higher on the similarity metric. For example, assuming ice-cream was assigned to the offer 2-4-1 category (amongst other categories), it is unlikely to be found to be similar to other items in that category, such as sausages, soft drinks, chocolate bars etc. However, ice-cream should be found to be similar to other products in a frozen dairy dessert category. It can be appreciated that the process carried out by block420analyses the items composing a category, rather than the category itself, which helps eliminate the influence of less relevant categories in determining a substitute item. In other words, an analysis of the items themselves is best placed to determine the primary category.

Block430may compute topic embedding metrics, using LDA for example, based on a concatenation of the item names and their respective descriptions. Block430may compute sentence embedding metrics, using Global Vectors, GloVe, for example based on a concatenation of the item names and their respective descriptions. The GloVe sentence embeddings may undergo dimension reduction to reduce processing burden by reducing the size of the GloVe sentence embedding metrics by extracting relevant information and disposing the rest of the information as noise. One suitable technique for dimension reduction may be Principal Component Analysis, PCA. PCA is a projection based method which transforms the data by projection it onto a set of orthogonal axes.

At least one of the outputs of blocks420,430, and440may be input to machine learning model450, which may be a random forest classifier. Block450may process the outputs of blocks420,430, and440to deduce the most relevant, or primary category of each item. Machine learning model450may be trained using supervised learning using training data comprising a primary category for each item of a subset of the plurality of items. Deducing the primary category for each item can be used to reduce the number of substitutes that have to be further processed to identify the “best” substitutes.

As well as or instead of deducing the primary category, the model may also deduce the primary category tree. A category tree may include a primary category, a primary parent category, and a primary grandparent category. For example, an item may have a primary category of yogurt, a parent primary category of breakfast, and a primary grandparent category of healthier living.

Alternatively, in a computationally simpler implementation, blocks430,440, and450may be dispensed with and the similarity metric alone can be used to deduce the primary category and/or the primary category tree.

FIG.5shows a processing diagram500of block130in detail. Block510may receive data of the items including at least one of the item to be substituted and each similar item (i.e. the pairings produced by block110), a plurality of back-of-pack tags of the item to be substituted and a plurality of back-of-pack tags of each similar item, or a name of the item to be substituted and a name of each similar item.

Block520may compute a similarity metric, such as the Jaccard index or Jaccard similarity index between the primary categories of each item of an item pairing. The primary categories can be deduced using block120or the process flow ofFIG.4.

Block530may compute topic embedding metrics, using LDA for example, based on the plurality of back-of-pack tags of the item to be substituted and a plurality of back-of-pack tags of each similar item. Block540may compute sentence embedding metrics, using Global Vectors, GloVe, for example based on the name of the item to be substituted and a name of each similar item. Dimension reduction may be employed to reduce the processing burden of the GloVe embeddings.

At least one of the outputs of blocks520,530, and540may be input to machine learning model550, which may be a random forest classifier. Block550may process the outputs of blocks520,530, and540to deduce acceptable pairings (or potential substitutes). Machine learning model550may be trained using supervised learning using training data comprising both acceptable and unacceptable pairings. Typically, such training data cannot be derived from that provided by a retailer, assuming the retailer has a system of deciding fixed substitutes. A retailer typically only issues what it considers to be acceptable or “good” substitutes that have a low rejection rate. However, training model550on such a data set means it will not be able to discriminate between “good” and “bad” substitutes. Instead, the model450will learn how to discriminate between “good” and less “good” substitutes. The inventors have found that customizing the training data to include both “good” and “bad” substitutes greatly improves the trained model's performance. Introducing “bad” substitutes to a retailer's existing fixed list of substitutes is sufficient. Thus, block130and process500represent an important step in identifying “good” substitutes since existing rejection rates are not considered, which otherwise would result in overfitting.

The acceptable pairings output from block550may be input to block560to prioritize the number of pairings. Each pairing may have additional data supplemented such as primary category, or primary category tree, brand, and unit size etc. The more matching additional data each pairing has, the higher that pairing is prioritized. Only the top priority pairings may be submitted to block140. For example, if three pairings have matching additional data in three areas (i.e. primary category, brand, and unit size), they will be marked as priority 1, whereas a further 3 items that only match in two areas will be marked as priority 2. It will be appreciated that this is an optional step that serves to filter the number of potential substitute items that have to be evaluated by block120. Alternatively block560may be applied after the processing of block140or process600referenced below.

FIG.6shows a diagram600of block150in detail. Block610may receive data of the items including at least one of a first subset comprising at least one: of a name of the item to be substituted and a name of each similar item of the potential substitutes, a description of the item and a description of each similar item of the potential substitutes, or a primary category of the item and a primary category of each similar item of the potential substitutes (which can be derived from block120or process400); a customer revenue segment of the item to be substituted and a customer revenue segment of each similar item of the potential substitutes; back-of-pack tags of the item to be substituted and back-of-pack tags of each similar item of the potential substitutes; a second subset comprising at least one of: a unit-of-measure of the item to be substituted and a unit-of-measure of each similar item of the potential substitutes, a price of the item to be substituted and a price of each similar item of the potential substitutes, or a sales trend of the item to be substituted and a sales trend of each similar item of the potential substitutes; or a rejection rate of each similar item of the potential items when selected as a substitute of the item to be substituted. The rejection rate may be based on historical data of the item such as how often it was rejected when offered as a substitute to the item to be substituted. The rejection rate may include timestamped data to allow for seasonal variations, and other data inferences. The rejection rate may also include data from retailer initiated rejections (i.e. rejected before the item is offered to the customer).

Block620may compute sentence embedding metrics, using Global Vectors, GloVe, for example based on the first subset. Dimension reduction may be employed to reduce the processing burden of the GloVe embeddings. Block630may compute topic embedding metrics, using LDA for example, based on the customer revenue segment of the item to be substituted and a customer revenue segment of each similar item of the potential substitutes. Block640may compute topic embedding metrics, using LDA for example, based on the plurality of back-of-pack tags of the item to be substituted and a plurality of back-of-pack tags of each similar item. Block650may compute Bayesian updates to define a rejection rate metric. At least one of the outputs of blocks620,630,640,640or the second subset may be input to machine learning model660, which may be a random forest regressor. The output of block660is a predicted rejection rate of each substitute of the potential substitutes. The predicted rejection rate can be used to rank the potential substitutes such that the lower the likelihood of rejection, the higher a potential substitute is ranked. Other factors can be considered and weighted in the ranking process, such as the output of block560and/or specific retailer requirements. In one example, the predicted rejection rate may have a first weight, the output of block560a second weight, and retailer requirements (such as a price similarity) a third weight. Machine learning model660may be trained using supervised learning using training data comprising actual retailer rejection rates for items when offered as substitutes for an item to be substituted.

Whilst the processing carried out by block120and shown in diagram300can be used to carry out an initial filtering step, this processing can be omitted. This may mean that the remaining blocks (i.e.130,140,400, and500) process a larger set of data (i.e. all items). Although this may increase the processing burden of the remaining blocks, the processing of blocks120and300is not required, so the overall time taken and processing resources may not increase.

The processes/models shown inFIGS.1-6may be run on a periodic basis and the potential substitutes for each item can be stored in a look-up table or database for example. It may be advantageous to run each block at different intervals. For example, blocks120,140,300, and400may not need to be run in real-time. Rather, these blocks may be run periodically, at a first interval, and their outputs (i.e. determining similar items, and the primary category of each item) may be stored in a look-up table and/or database. Similarly, blocks120,140,300, and400may be run and re-trained periodically based on up-to-date data sets. Blocks130,150,500, and600may be run periodically, at a second interval. The first interval may be greater than the second interval since similar items and primary categories are less subject to change on a day-to-day basis, whereas data relevant to the potential substitutes and ranking thereof can change on a day-to-day basis. Therefore, using different intervals reduces the overall computational processing burden. Accordingly, blocks130and500may be run at the second interval, whereas blocks150and600may be run at a third interval, where the third interval is less than the second interval. Similarly, blocks130,150,500, and600may be re-trained periodically based on up-to-date data sets. It may be advantageous to re-train blocks130,150,400and600using data generated over a rolling period. For example, the most recent rejection data generated by a retailer can be used to re-train blocks150and600.

It will also be appreciated from the processes shown inFIGS.1, and3-6that there is provided a method700of training machine learning models for determining a substitute for an item of a plurality of items, as shown inFIG.7. In step710, a first set of training data comprising at least one of names, descriptions, or categories of the plurality of items, is provided. In step720, a first machine learning model is trained using the first set of training data, to identify at least one similar item to each item of the plurality of items. In step730, a second set of training data comprising a primary category for each item of a subset of the plurality of items, is provided. In step740, a third set of training data comprising pairings of items comprising acceptable pairings and unacceptable pairings, is provided. In step750, a third machine learning model is trained using the third set of training data, to determine potential substitutes. In step760, a fourth set of training data comprising rejection rates of the plurality of items, is provided. In step770, a fourth machine learning model is trained using the fourth set of training data, to rank the potential substitutes based on a rejection probability of each of the potential substitutes.

It will be appreciated that the processes/methods described above inFIGS.1-7are not limited to a system that determines substitutes per se. Rather, the processes/methods above allow equivalent items to be determined. That is, items that are as identical as possible in terms of properties of the items, can be identified.

A system800for performing the processes/methods ofFIGS.1-7is shown inFIG.8. A training module810is suitably programmed to carry out the training processes ofFIGS.1, and3-7by interfacing with central processing unit, CPU,820, graphical processing unit, GPU,830, memory or random access memory, RAM840, and solid state drive, SSD, and/or hard disc drive, HDD, and or a cloud computing environment,850. CPU820may execute the steps of the processes ofFIGS.1, and3-7which concern inputting the training data sets to the respective machine learning models. GPU830may execute the processes/methods ofFIGS.1-7which concern executing the machine learning models. RAM840may be accessed as appropriate by the training module810. The training data may be provided by SSD/HDD/CLOUD850. The training module810may also interact with trained model module860. The trained model module860carries out the processes/methods ofFIGS.1-6. The trained model module860also interfaces with each of the CPU820, GPU830, RAM840, and SSD/HDD/CLOUD850. The CPU820may perform the metric processing ofFIGS.1-6, whereas GPU830may execute the processes/methods ofFIGS.1-6which concern executing the trained models via the trained model module860. The data concerning a number of items, where at least one item is to be substituted may be provided by SSD/HDD/CLOUD850. It will be appreciated that each of the CPU820, GPU830, RAM840, SSD/HDD/CLOUD850, training module810, and trained model module860may be implemented as discrete elements either in a single location, or across multiple locations using a cloud computing environment. Example cloud computing environments include Amazon Web Services™, Microsoft Azure™, Google Cloud Platform™, and IBM Cloud™.

The CPU810may interface with instruction module870to indicate at least one substitute item (as determined by the processes/methods ofFIGS.1-6) for an item to be substituted. The instruction module may interact with the system900ofFIG.9to generate a user interface910. The system ofFIG.9can take the form of a user device such as an electronic device or smartphone (running iOS™ or Android™, provided by Apple™ and Google™ respectively), or a virtual reality headset, or an augmented reality headset. The user device may have an interactive display which can output information and receive and/or respond to a user input. The user device may also have a wireless communication system such as a cellular network and/or Wi-Fi™, and/or near-field communication, and/or Bluetooth™. The user interface may show an item to be substituted920and accompanying information930, such as item description, brand unit of measurement, price etc. A ranked list of substitutes940, as generated by the processes and methods ofFIGS.1-6is also displayed. Each substitute950may have respective accompanying information such as item description, brand unit of measurement, price etc. Each substitute may also have an accompanying user interface input element960to indicate acceptance and/or rejection of the substitute. In the example shown, the filled-in input elements are used to indicate the acceptance or rejection of an item. A user can therefore approve the substitute before it is integrated into an original list of items (e.g. a customer of order) to take the place of an item to be substituted. Alternatively, system900may be configured to automatically integrate the top ranked item in the original list of items. That is, the system900does not require the user interface input to approve and/or reject the item. In such a case, system900is optional. As yet another alternative, user interface920may be presented periodically for user input. In any case, the user input can be fed into blocks610and650to update the rejection rate that is used by block660to predict the rejection rate. It will also be appreciated that a further user interface can be provided for the purpose of instructing a picker on a substitute for an item to be substituted. Such a user interface will indicate the item to be substituted and a ranked list of the order in which each of the substitute item should be attempted to be obtained by the picker. That is, the picker should go to a location to obtain the top ranked item, and if not available proceed to the next ranked item, and so on until a substitute item is obtained. The picker may be required by the further user interface to confirm which substitute has been picked, such as by capturing an image using the system on which the further user interface is displayed. The further user interface may enable the picker to open a two-way communication with a retailer to discuss the substitute to be picked.

System800and/or system900can be used as part of a fully automated end-to-end system1000as shown inFIG.10. System1000may have an online interface1010for receiving a list of items1005(e.g. a customer of order). Interface1010may interact with a real-time stock inventory1020to determine that an item of the list of items is not available (i.e. out of stock), and is to be substituted. Upon determining this, interface1010interacts with system800to determine a substitute. Upon determining at least one substitute, system800optionally outputs at least one substitute to system900. Upon confirming the substitute is acceptable (either automatically by being the top ranked substitute, or via user interface910), interface1010updates the list of items to replace the item to be substituted with the accepted/confirmed substitute. Interface1010then interacts with an automated storage and retrieval system, ASRS,1030to automatically retrieve and prepare the items (including at least one substitute) for shipping. An ASRS may be of the type described in WO2015019055A1 (“Ocado”), hereby incorporated by reference, where robotic load handling devices operate on a grid structure to automatically retrieve item for shipping. In general any automated system can be used.

Additional Considerations

The preceding description is provided to enable any person skilled in the art to practice the various embodiments described herein. The examples discussed herein are not limiting of the scope, applicability, or embodiments set forth in the claims. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments. For example, changes may be made in the function and arrangement of elements discussed without departing from the scope of the disclosure. Various examples may omit, substitute, or add various procedures or components as appropriate. For instance, the methods described may be performed in an order different from that described, and various steps may be added, omitted, or combined. Also, features described with respect to some examples may be combined in some other examples. For example, an apparatus may be implemented or a method may be practiced using any number of the aspects set forth herein. In addition, the scope of the disclosure is intended to cover such an apparatus or method that is practiced using other structure, functionality, or structure and functionality in addition to, or other than, the various aspects of the disclosure set forth herein. It should be understood that any aspect of the disclosure disclosed herein may be embodied by one or more elements of a claim.

As used herein, the word “exemplary” means “serving as an example, instance, or illustration.” Any aspect described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other aspects.

As used herein, a phrase referring to “at least one of” a list of items refers to any combination of those items, including single members. As an example, “at least one of: a, b, or c” is intended to cover a, b, c, a-b, a-c, b-c, and a-b-c, as well as any combination with multiples of the same element (e.g., a-a, a-a-a, a-a-b, a-a-c, a-b-b, a-c-c, b-b, b-b-b, b-b-c, c-c, and c-c-c or any other ordering of a, b, and c).

As used herein, the term “determining” encompasses a wide variety of actions. For example, “determining” may include calculating, computing, processing, deriving, investigating, looking up (e.g., looking up in a table, a database or another data structure), ascertaining and the like. Also, “determining” may include receiving (e.g., receiving information), accessing (e.g., accessing data in a memory) and the like. Also, “determining” may include resolving, selecting, choosing, establishing and the like.

The methods disclosed herein comprise one or more steps or actions for achieving the methods. The method steps and/or actions may be interchanged with one another without departing from the scope of the claims. In other words, unless a specific order of steps or actions is specified, the order and/or use of specific steps and/or actions may be modified without departing from the scope of the claims. Further, the various operations of methods described above may be performed by any suitable means capable of performing the corresponding functions. The means may include various hardware and/or software component(s) and/or module(s), including, but not limited to a circuit, an application specific integrated circuit (ASIC), or processor. Generally, where there are operations illustrated in figures, those operations may have corresponding counterpart means-plus-function components with similar numbering.

The following claims are not intended to be limited to the embodiments shown herein, but are to be accorded the full scope consistent with the language of the claims. Within a claim, reference to an element in the singular is not intended to mean “one and only one” unless specifically so stated, but rather “one or more.” Unless specifically stated otherwise, the term “some” refers to one or more. No claim element is to be construed under the provisions of 35 U.S.C. § 112 (f) unless the element is expressly recited using the phrase “means for” or, in the case of a method claim, the element is recited using the phrase “step for.” All structural and functional equivalents to the elements of the various aspects described throughout this disclosure that are known or later come to be known to those of ordinary skill in the art are expressly incorporated herein by reference and are intended to be encompassed by the claims. Moreover, nothing disclosed herein is intended to be dedicated to the public regardless of whether such disclosure is explicitly recited in the claims.