INTERACTIVE CONCEPT EDITING IN COMPUTER-HUMAN INTERACTIVE LEARNING

• US 20150019211A1
• Filed: 11/08/2013
• Published: 01/15/2015
• Est. Priority Date: 07/12/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: SIMARD, PATRICE Y., GRANGIER, DAVID G., BOTTOU, LEON, AMERSHI, SALEEMA A.
• Granted Patent: US 10,372,815 B2
• Time in Patent Office: Days
• US Class Current: 704/10
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 1/0072 Error control for data other than payload data, e.g. control data
• CPC Class Codes: H04L 1/0079 Formats for control data H04L1/16 takes precedence; training sequences H04L25/00 and H04L27/00

Abstract

A collection of data that is extremely large can be difficult to search and/or analyze. Relevance may be dramatically improved by automatically classifying queries and web pages in useful categories, and using these classification scores as relevance features. A thorough approach may require building a large number of classifiers, corresponding to the various types of information, activities, and products. Creation of classifiers and schematizers is provided on large data sets. Exercising the classifiers and schematizers on hundreds of millions of items may expose value that is inherent to the data by adding usable meta-data. Some aspects include active labeling exploration, automatic regularization and cold start, scaling with the number of items and the number of classifiers, active featuring, and segmentation and schematization.

Claims

1. One or more computer-readable media having embodied thereon computer-usable instructions that, when executed, facilitate a method of interactively generating dictionaries for machine learning, the method comprising:

presenting a user interface for generating a dictionary that includes a list of one or both of words or n-grams that define a concept usable as a feature for training a classifier;

presenting on the user interface a positive-example field configured to receive user-input words or n-grams that are positive examples of the concept, wherein the positive examples are received from one or more of

A) a typed entry or

B) a selection of one or more suggested words or n-grams from

one or more suggestion-set fields; and

presenting on the user interface the one or more suggestion-set fields configured to display one or more system-generated lists that contain suggested words or n-grams that are selectable for inclusion in the positive-example field.

2. The media of claim 1, the method further comprising:

receiving a first user-input word or n-gram that is a first positive example of the concept;

presenting a list of suggested words or n-grams that represent a generalized concept generated based at least on the first positive example of the concept.

3. The media of claim 2, the method further comprising:

subsequent to presenting the list of suggested words or n-grams, receiving a second user-input word or n-gram that is a second positive example of the concept;

refining the list of suggested words or n-grams based at least on a combination of the first positive example and the second positive example; and

presenting the refined list of suggested words or n-grams that represent a refined generalized concept.

4. The media of claim 2, the method further comprising:

presenting on the user interface a negative-example field configured to receive user-input words or n-grams that are negative examples of the concept, wherein the negative examples are received from one or more of

A) a typed entry, or

B) a selection of one or more suggested words or n-grams from

one or more suggestion-set fields;

subsequent to presenting the list of suggested words or n-grams, receiving a second user-input word or n-gram that is a negative example of the concept;

refining the list of suggested words or n-grams based at least on a combination of the first positive example and the negative example; and

presenting the refined list of suggested words or n-grams that represent a refined generalized concept.

5. The media of claim 2, the method further comprising:

receiving a user selection of one or more words or n-grams from a suggestion-set field; and

including the user-selected one or more words or n-grams from the first suggestion set in the positive example field.

6. The media of claim 1, wherein each word or n-gram in the dictionary is assigned a respective weight.

7. The media of claim 6, wherein the respective weight of each word or n-gram is scaled by a function of frequency and dictionary size based on training data during generation of the dictionary.

8. The media of claim 7, wherein the scaled weights are related by a regularization constraint that adjusts the weights of the words that have less training data toward a value determined by the words that have more training data.

9. One or more computer-readable media having embodied thereon computer-usable instructions that, when executed, facilitate a method of interactively generating dictionaries for machine learning, the method comprising:

presenting a user interface for generating dictionaries, wherein a dictionary includes a list of n-grams that define a concept, and wherein the dictionary is usable as a feature for training a classifier;

presenting, on the user interface, a positive-example input field configured to receive user-input n-grams that are positive examples of the concept;

presenting on the user interface one or more suggestion-set fields configured to display one or more system-generated lists of suggested n-grams;

receiving one or more user-input n-grams that are positive examples of the concept;

generating a first set of suggested n-grams that represent a first generalized concept based on the one or more user-input positive examples; and

presenting the first set of suggested n-grams in a first suggestion-set field on the user interface.

10. The media of claim 9, the method further comprising:

generating a refinement of the first set of suggested n-grams that represents a refinement of the first generalized concept based on at least one or more additional user-input positive examples; and

presenting the refinement of the first set of suggested n-grams on the user-interface.

11. The media of claim 10, the method further comprising:

repeating the steps of generating the refinement and presenting the refinement until an indication is received that the user has finished editing the dictionary; and

saving the contents of the positive-example input field in a dictionary.

12. The media of claim 9, the method further comprising:

generating a second set of suggested n-grams that represent a second generalized concept based on the one or more user-input n-grams; and

presenting the second set of suggested n-grams.

13. The media of claim 12, wherein the first set of suggested n-grams is generated utilizing a first source.

14. The media of claim 13, wherein the second set of suggested n-grams is generated utilizing a second source.

15. The media of claim 13, wherein the first source includes one or more of:

A) a previously-stored dictionary;

B) a click graph representing queries and visited web pages;

C) content of a table found on the world-wide web;

or

D) semantic representations of words.

16. The media of claim 9, the method further comprising:

presenting on the user interface a negative-example input field configured to receive user-input n-grams that are negative examples of the concept.

17. The media of claim 16, the method further comprising:

receiving one or more user-input n-grams that are negative examples of the concept;

generating a refinement of the first set of suggested n-grams that represents a second generalized concept based at least on the one or more user-input negative examples; and

presenting the refinement of the first set of suggested n-grams on the user-interface.

18. One or more computer-readable media having embodied thereon computer-usable instructions that, when executed, facilitate a method of interactively generating dictionaries for machine learning, the method comprising:

generating an interface for editing dictionaries, wherein a dictionary includes a list of words that define a concept usable as a feature for training a classifier;

presenting on the interface a positive-example input field configured to receive user-input words that are positive examples of the concept;

presenting on the user interface a negative-example input field configured to receive user-input words that are negative examples of the concept;

presenting on the user interface a suggestion-set field configured to display a system-generated list of suggested words, wherein the list of suggested words represents a generalized concept based on words in one or both of the positive-example input field or the negative-example field;

receiving one or more user-input words that are positive or negative examples of the concept, wherein the one or more user-input words are received from one or more of

A) a typed entry, or

B) a selection of one or more suggested words from the suggestion-set field;

generating a set of suggested words that represent a generalized concept based on the one or more user-input positive or negative examples;

presenting the set of suggested words in the suggestion-set field on the user interface;

receiving a user selection of a first suggested word from the set of suggested words;

including the first suggested word in the positive-example field or the negative-example field;

refining the set of suggested words based at least on the first suggested word that was included in the positive-example field or the negative-example field;

presenting the refined set of suggested words in the first suggestion-set field;

receiving an indication that the user has finished editing the dictionary; and

saving the contents of the positive-example input field in a dictionary.

19. The media of claim 18, the method further comprising:

presenting on the user interface one or more input fields configured to receive one or more of

A) a user-selection that indicates whether trainable parameters are associated with each word in the dictionary or whether there is one trainable parameter associated with the entire dictionary,

B) a user selection that indicates whether a feature value associated with the dictionary is a binary value based on a quantity of dictionary words or whether the feature value is a pre-determined function of a frequency of dictionary words,

C) a user selection that indicates whether word frequencies are normalized,

D) a user selection that indicates a regularization threshold that regulates a degree of interrelatedness between respective weights assigned to words in the dictionary, or

E) a user selection that indicates whether the feature value is higher when multiple words from the dictionary appear within a document or when a single word from the dictionary appears multiple times in the document.

20. The media of claim 18, wherein each word in the dictionary is assigned a respective weight, and wherein the weights are related by a regularization constraint that adjusts the weights of words that have less training data toward a value determined by words that have more training data.