Artificial intelligence system and method for auto-naming customer tree nodes in a data structure

• US 10,678,769 B2
• Filed: 08/06/2019
• Issued: 06/09/2020
• Est. Priority Date: 08/06/2018
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Inventors: Karmakar, Somedip, Das, Amlan Jyoti, Sudhodanan, Aloka
• Primary Examiner(s): Park, Grace
• Application Number:
  US16/533,091
• Publication Number:
  US 20200042508A1
• Time in Patent Office: 308 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities

Abstract

Systems and methods for auto-naming nodes in a behavior tree are provided. An example method can include: providing a hierarchy of tree nodes by a computing device; generating a first corpus for each node at a final level; creating a first term-document matrix associated with the first corpus; identifying a first group of high-frequency words in the first term-document matrix; removing the first group of the high-frequency words obtain a second corpus; creating a second term-document matrix based on each of a set of predefined rules; identifying a second group of high-frequency words to represent node names; selecting a best set of the predefined rules based on an automatic evaluation model; generating a node name by removing a duplicate word in each node; incorporating feedback to generate a predicted name for each node; and selecting a final name for each node from the predicted name and the generated node name.

Claims

1. A computer-implemented method for auto-naming customer behavior tree (CBT) nodes, comprising:

providing, by a computing device, a hierarchy of nodes at a plurality of levels of the CBT;

generating, by a processor, a first corpus comprising product description of all items in a category and product attributes for each node of a final level of the CBT;

creating, based on the first corpus, a first term-document matrix associated with each word in the first corpus and a frequency that the word appears in the first corpus;

identifying a first group of high-frequency words in the first term-document matrix;

removing the first group of the high-frequency words from the first corpus to obtain a second corpus;

creating a second term-document matrix associated with the second corpus based on each of a set of predefined rules, a value of the second term-document matrix being defined as a data set to represent a number of times each word appears in the second corpus, the set of the predefined rules comprising at least one of an n-gram frequency model, a common themes topic model, an overlapping topic model, a word vector representation model, and a full text approach model;

identifying, based on a data set of the second term-document matrix, a second group of high-frequency words to represent node names such that the second group of the high-frequency words satisfy a predefined frequency cut-off threshold;

selecting, by the processor, a best set of the predefined rules based on an automatic evaluation model;

generating a node name associated with the second group of the high-frequency words by removing a duplicate word in each node, using the best set of the predefined rules and based on a frequency ratio of each word in each node to all the nodes;

incorporating feedback associated with other nodes in the category to generate a predicted name for each node; and

selecting a final name for each node from the predicted name and the generated node name associated with the second group of the high-frequency words.

2. The method of claim 1, wherein the attributes comprise brand, fineline, price bucket, latent topics from product description, size and case package.

3. The method of claim 1, wherein, based on the n-gram frequency model, the set of predefined rules comprises:

converting, using the n-gram frequency model with an n-gram tokenizer, the second corpus into the data set of an n-gram sequence, wherein an n-gram sequence comprises at least one of 4-gram, trigram, bigram, and unigram;

selecting, by the n-gram frequency model, n-grams that have a frequency higher or equal to a predefined frequency cut-off threshold; and

identifying, based on the selecting, the second group of high-frequency words in the data set to represent the node names such that the high-frequency words satisfy the predefined frequency cut-off threshold.

4. The method of claim 1, wherein the first group of high-frequency words is commonly used for all nodes in the hierarchy and the predefined frequency cut-off threshold is 90%.

5. The method of claim 1, wherein, based on the common themes topic model, the set of predefined rules comprises:

removing infrequent words with extreme sparsity more than 99% from the second term-document matrix associated with the second corpus;

obtaining 10 clusters for a node by applying with Latent Dirichlet Allocation model and Gibbs sampling; and

choosing top-occurring common words across different clusters to get a central overlapping word for the node.

6. The method of claim 1, wherein, based on the overlapping topic model, the set of predefined rules comprises:

removing words with extreme sparsity more than 99% from the first term-document matrix associated with the first corpus;

obtaining clusters for all nodes of the final level of CBT by applying with Latent Dirichlet Allocation model with Gibbs sampling, a number of the cluster being equal to the number of the nodes of the final level; and

assigning each node of the final level of CBT with a word of a highest allocation probability.

7. The method of claim 1, wherein, based on the word vector representation model, the set of predefined rules comprises:

obtaining a data set of n-gram sequence on a rollup description of a node with window-size 12, 5 iterations, and 4 threads to create 200-dimention vectors, wherein the n-gram sequence comprises at least one of 4-gram, trigram, bigram, and unigram;

selecting the data set of the n-gram sequence occurring in a particular node and calculating a centroid of these vector representations; and

selecting the words closest to a centroid of the node as a name of the node.

8. The method of claim 1, wherein, based on a graph-based model, the set of predefined rules comprises:

importing roll-up ID description and important attributes comprising fineline description, brand Name, brand type, and weight description;

creating one additional variable from a pack number to detect multipack and single-pack items and concatenating information together to create a final data; and

selecting a word for a node which receives more links thank other words.

9. The method of claim 1, wherein, based on a full text approach model, the set of predefined rules comprises:

generating a corpus by concatenating roll up ID description, fineline description, and price bucket;

removing stop words and stemming from the corpus;

generating a document term frequency matrix using count vectorizer where a corresponding full text of each rollup ID is treated as a separate document;

normalizing the frequency by dividing a word frequency by a total number of documents to obtain a relevance; and

selecting words with a normalized frequency above a certain threshold of 0.8 to be title words.

10. The method of claim 1, wherein the incorporating the feedback further comprises:

receiving, via a display screen, the feedback associated with each node of the final level of the CBT;

generating, using a co-training model and based on the second group of high-frequency words, the predicted name for each node;

comparing a prediction probability of the predicted name to a predefined prediction threshold for selecting the final name for each node; and

when the prediction probability of the predicted name is larger than predefined prediction threshold, selecting the predicted name as the final name for the node.

11. A system for auto-naming customer behavior tree (CBT) nodes, comprising:

a processor of a computing device; and

a computer program product comprising a non-transitory computer-readable storage medium having instructions stored which, when executed by the processor, cause the processor to perform operations comprising;

providing, by a computing device, a hierarchy of nodes at a plurality of levels of the CBT;

generating a first corpus comprising product descriptions of all items in a category and product attributes for each node of a final level of the CBT;

creating, based on the first corpus, a first term-document matrix associated with each word in the first corpus and a frequency that the word appears in the first corpus;

identifying a first group of high-frequency words in the first term-document matrix;

removing the first group of the high-frequency words, the first corpus to obtain a second corpus;

creating a second term-document matrix associated with the second corpus based on each of a set of predefined rules, a value of the second term-document matrix being defined as a data set to represent a number of times each word appears in the second corpus, the set of predefined rules comprising at least one of an n-gram frequency model, a common themes topic model, an overlapping topic model, a word vector representation model, and a full text approach model;

identifying, based on a data set of the second term-document matrix, a second group of high-frequency words to represent node names such that the second group of the high-frequency words satisfy a predefined frequency cut-off threshold;

choosing a best set of the predefined rules based on an automatic evaluation model;

generating a node name associated with the second group of the high-frequency words by removing a duplicate word in each node, based on a frequency ratio of each word in each node to all the nodes;

incorporating feedback associated with the nodes in the category to generate a predicted name for each node; and

selecting a final name for each node from the predicted name and the generated node name associated with the second group of the high-frequency words.

12. The system of claim 11, wherein the attributes comprise brand, fineline, price bucket, latent topics from product description, size and case packs.

13. The system of claim 11, wherein, based on the n-gram frequency model, the set of predefined rules comprises:

converting, using the n-gram frequency model with an n-gram tokenizer, the second corpus into the data sets of an n-gram sequence, wherein an n-gram sequence comprises at least one of 4-gram, trigram, bigram, and unigram;

selecting, by the n-gram frequency model, n-grams that have a frequency higher or equal to a predefined frequency cut-off threshold; and

identifying, based on the selecting, the second group of high-frequency words in the data set to represent the node names such that the high-frequency words satisfy the predefined frequency cut-off threshold.

14. The system of claim 11, wherein the first group of high-frequency words is commonly used for all nodes in the hierarchy and the predefined frequency cut-off threshold is 90%.

15. The system of claim 11, wherein, based on the common themes topic model, the set of predefined rules comprises:

removing infrequent words with extreme sparsity more than 99% from the second term-document matrix associated with the second corpus;

obtaining 10 clusters for a node by applying with Latent Dirichlet Allocation model and Gibbs sampling; and

choosing top-occurring common words across different clusters to get a central overlapping word for the node.

16. The system of claim 11, wherein, based on the overlapping topic model, the set of predefined rules comprises:

removing words with extreme sparsity more than 99% from the first term-document matrix associated with the first corpus;

obtaining clusters for all nodes of the final level of CBT by applying with Latent Dirichlet Allocation model with Gibbs sampling, a number of the cluster being equal to the number of the nodes of the final level; and

assigning each node of the final level of CBT with a word of a highest allocation probability.

17. The system of claim 11, wherein, based on the word vector representation model, the set of predefined rules comprises:

obtaining a data set of n-gram sequence on a rollup description of a node with window-size 12, 5 iterations, and 4 threads to create 200-dimention vectors, wherein the n-gram sequence comprises at least one of 4-gram, trigram, bigram, and unigram;

selecting the data set of the n-gram sequence occurring in a particular node and calculating a centroid of these vector representations; and

selecting the words closest to a centroid of the node as a name of the node.

18. The system of claim 11, wherein, based on a graph-based model, the set of predefined rules comprises:

importing rollup ID description and important attributes comprising fineline description, brand Name, brand type, and weight description;

creating one additional variable from a pack number to detect multipack and single-pack items and concatenating together to create a final data; and

selecting a word for a node which receives more links thank other words.

19. The system of claim 11, wherein, based on the full text approach model, the set of predefined rules comprises:

generating a corpus by concatenating roll-up ID description, fineline description, and price bucket;

removing stop words and stemming from the corpus;

generating a document term frequency matrix using count vectorizer where a corresponding full text of each roll-up ID is treated as a separate document; and

normalizing the frequency by dividing a word frequency by a total number of documents to obtain a relevance; and

selecting words with a normalized frequency above a certain threshold of 0.8 to be title words.

20. The system of claim 11, wherein the incorporating the feedback further comprises:

receiving, via a display screen, the feedback associated with each node of the final level of the CBT;

generating, using a co-training model and based on the second group of high-frequency words, the predicted name for each node;

comparing a prediction probability of the predicted name with a predefined prediction threshold for selecting the final name for each node; and

when the prediction probability of the predicted name is larger than predefined prediction threshold, selecting the predicted name as the final name for the node.