System and method for determining semantically related terms using an active learning framework

• US 8,275,722 B2
• Filed: 03/10/2010
• Issued: 09/25/2012
• Est. Priority Date: 04/30/2007
• Status: Active Grant

• Current Assignee: Slack Technologies, Inc. (Salesforce.com, Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Jhala, Pradhuman, He, Xiaofei
• Primary Examiner(s): Starks, Wilbert L
• Application Number:
  US12/721,358
• Publication Number:
  US 20100169249A1
• Time in Patent Office: 930 Days
• Field of Search: 706/12, 706/45, 370/468, 370/428, 704/10
• US Class Current: 706/12
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Systems and methods for determining semantically related terms using an active learning framework such as Transductive Experimental Design are disclosed. Generally, to enhance a keyword suggestion tool, an active learning module trains a model to predict whether a term is relevant to a user. The model is then used to present the user with terms that have been determined to be relevant based on the model so that an online advertisement service provider may more efficiently provide a user with terms that are semantically related to a seed set.

Claims

1. A computer-implemented method for determining semantically related terms, the method comprising:

presenting, with a processor, one or more terms of a first plurality of semantically related terms to a user based on a predictive error of each term of the first plurality of semantically related terms;

receiving, with a processor, an indication of relevance of at least one of the terms of the first plurality of semantically related terms presented to the user;

training a model, with a processor, to predict an indication of relevance of a term by the user based on the received indication of relevance of at least one of the terms of the first plurality of semantically related terms presented to the user;

receiving a second plurality of semantically related terms from a keyword suggestion tool; and

presenting, with a processor, one or more terms of the second plurality of semantically related terms to the user based on the model and one or more properties of each term of the second plurality of semantically related terms.

2. The computer-implemented method of claim 1, wherein presenting one or more terms of the first plurality of semantically related terms to a user based on a predictive error of each term of the first plurality of semantically related terms comprises:

determining a subset of terms of the first plurality of semantically related terms based on a predictive error of each term; and

presenting the subset of terms to the user.

3. The computer-implemented method of claim 1, where a predictive error of a term is calculated using the equation:

err(x)=x^T(XX^T)<sup>−

1</sup>x

where x is a term vector associated with a term of the first plurality of semantically related terms and X is a matrix including a term vector for each term of the first plurality of semantically related terms.

4. The computer-implemented method of claim 1, wherein the one or more properties of each term of the second plurality of semantically related terms includes at least one of edit distance or word distance.

5. The computer-implemented method of claim 1, wherein presenting one or more terms of the second plurality of semantically related terms to the user based on the model and one or more properties of each term of the second plurality of semantically related terms comprises:

extracting one or more properties of a term of the second plurality of semantically related terms;

determining a predicted indication of the relevance of the term based on the extracted properties and the model; and

comparing the predicted indication of relevance of the term to a threshold.

6. The computer-implemented method of claim 1, further comprising:

receiving an indication of relevance of at least one of the one or more terms presented to the user from the second plurality of semantically related terms; and

adjusting the model based on the received indication of relevance of at least one term presented to the user from the second plurality of semantically related terms.

7. The computer-implemented method of claim 6, further comprising:

receiving a third plurality of semantically related terms form the keyword suggestion tool; and

presenting one or more terms of the third plurality of semantically related terms to the user based on the adjusted model and one or more properties of each term of the third plurality of semantically related terms.

8. A computer-readable storage medium comprising a set of instructions for determining semantically related terms, the set of instructions to direct a processor to perform acts of:

presenting one or more terms of a first plurality of semantically related terms to a user based on a predictive error of each term of the first plurality of semantically related terms;

receiving an indication of relevance of at least one of the one or more terms presented to the user from the first plurality of semantically related terms;

training a model to predict an indication of relevance of a term by the user based on the received indication of relevance of at least one of the one or more terms presented to the user from the first plurality of semantically related terms;

receiving a second plurality of semantically related terms from a keyword suggestion tool; and

presenting one or more terms of the second plurality of semantically related terms to the user based on the model and one or more properties of each term of the second plurality of semantically related terms.

9. The computer-readable storage medium of claim 8, wherein presenting one or more terms of the first plurality of semantically related terms to a user based on a predictive error of each term of the first plurality of semantically related terms comprises:

determining a subset of terms of the first plurality of semantically related terms based on a predictive error of each term; and

presenting the subset of terms to the user.

10. The computer-readable storage medium of claim 8, where a predictive error of a term is calculated using the equation:

err(x)=x^T(XX^T)<sup>−

1</sup>x

where x is a term vector associated with a term of the first plurality of semantically related terms and X is a matrix including a term vector for each term of the first plurality of semantically related terms.

11. The computer-readable storage medium of claim 8, wherein the one or more properties of each term of the second plurality of semantically related terms includes at least one of edit distance or word distance.

12. The computer-readable storage medium of claim 8, wherein presenting one or more terms of the second plurality of semantically related terms to the user based on the model and one or more properties of each term of the second plurality of semantically related terms comprises:

extracting one or more properties of a term of the second plurality of semantically related terms;

determining a predicted indication of the relevance of the term based on the extracted properties and the model; and

comparing the predicted indication of relevance of the term to a threshold.

13. The computer-readable storage medium of claim 8, further comprising a set of instructions to direct a processor to perform acts of:

receiving an indication of relevance of at least one of the one or more terms presented to the user from the second plurality of semantically related terms; and

adjusting the model based on the received indication of relevance of at least one term presented to the user from the second plurality of semantically related terms.

14. The computer-readable storage medium of claim 13, further comprising a set of instructions to direct a processor to perform acts of:

receiving a third plurality of semantically related terms form the keyword suggestion tool; and

presenting one or more terms of the third plurality of semantically related terms to the user based on the adjusted model and one or more properties of each term of the third plurality of semantically related terms.

15. A system for determining a semantically related term comprising:

a keyword suggestion tool comprising a processor and a storage medium, the keyword suggestion tool configured to determine a plurality of semantically related terms based on a seed set;

an active learning module comprising a processor and a storage medium that is in communication with the keyword suggestion tool, the active learning module configured to;

receive a first plurality of semantically related terms from the keyword suggestion tool;

select a first subset comprising at least one term of the first plurality of semantically related terms based on a predictive error of each term of the semantically related terms;

receive an indication of relevance from a user of at least one term of the first subset;

train a model to predict an indication of relevance of a term by the user based on the received indication of relevance of the at least one term of the first subset;

receive a second plurality of semantically related terms from the keyword suggestion tool; and

select a second subset comprising at least one term of the second plurality of semantically related terms based on the model and one or more properties of each term of the second plurality of semantically related terms.

16. The system of claim 15, where to select a second subset comprising at least one term of the second plurality of semantically related terms based on the model and one or more properties of each term of the second plurality of semantically related terms, the active learning module is further configured to:

extract one or more properties of a term of the second plurality of semantically related terms;

determine a predicted indication of relevance of the term based on the extracted properties and the model; and

compare the predicted indication of relevance of the term to a threshold.

17. The system of claim 15, wherein the one or more properties of each term of the second plurality of semantically related terms includes at least one of edit distance or word distance.

18. The system of claim 15, wherein the active learning module is further configured to:

receive an indication of relevance from the user of at least one term of the second subset; and

adjust the model based on the received indication of relevance of at least one term of the second subset.

19. The system of claim 18, wherein the active learning module is further operative to:

receive a third plurality of semantically related terms from the keyword suggestion tool; and

select a third subset comprising at least one term of the third plurality of semantically related terms based on the adjusted model and one or more properties of the third plurality of semantically related terms.