Interactive concept editing in computer-human interactive learning

• US 10,372,815 B2
• Filed: 11/08/2013
• Issued: 08/06/2019
• Est. Priority Date: 07/12/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Simard, Patrice Y., Grangier, David G., Bottou, Leon, Amershi, Saleema A.
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Chavez, Rodrigo
• Application Number:
  US14/075,679
• Publication Number:
  US 20150019211A1
• Time in Patent Office: 2,097 Days
• Field of Search: 704 7, 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 hardware computer-storage device 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 which receives user input that is utilized for generating a new dictionary that represents a single concept, wherein the new dictionary includes a list of one or both of words or n-grams that are positive examples of the single concept and is 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 single concept, wherein the user-input words or n-grams are utilized to determine a generalized concept that corresponds to the positive examples, and wherein the positive examples are received from one or more of

a typed entry or

a selection of one or more suggested words or n-grams from one or more suggestion-set fields;

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 generated based on the generalized concept, wherein the suggested words or n-grams are examples of the generalized concept, and wherein the suggested words or n-grams are selectable for inclusion in the positive-example field; and

presenting on the user interface a working set field configured to display words or n-grams added to a working set from the one or more suggestion-set fields, wherein the words or n-grams displayed in the working set field are saved in the new dictionary.

2. The one or more hardware computer-storage device 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 one or more hardware computer-storage device 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 one or more hardware computer-storage device 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 typed entry, or

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 one or more hardware computer-storage device 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 one or more hardware computer-storage device of claim 1, wherein each word or n-gram in the dictionary is assigned a respective weight.

7. The one or more hardware computer-storage device 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 one or more hardware computer-storage device 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. A method of interactively generating dictionaries for machine learning, the method comprising:

presenting a user interface which receives user input that is utilized for generating a new dictionary that represents a single concept, wherein the new dictionary includes a list of one or both of words or n-grams that are positive examples of the single concept and is 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 single concept, wherein the user-input words or n-grams are utilized to determine a generalized concept that corresponds to the positive examples, and wherein the positive examples are received from one or more of

a typed entry or

a selection of one or more suggested words or n-grams from one or more suggestion-set fields;

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 generated based on the generalized concept, wherein the suggested words or n-grams are examples of the generalized concept, and wherein the suggested words or n-grams are selectable for inclusion in the positive-example field; and

presenting on the user interface a working set field configured to display words or n-grams added to a working set from the one or more suggestion-set fields, wherein the words or n-grams displayed in the working set field are saved in the new dictionary.

10. The method of claim 9, 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.

11. The method of claim 10, 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.

12. The method of claim 10, 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 typed entry, or

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.

13. The method of claim 10, 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.

14. The method of claim 9, wherein each word or n-gram in the dictionary is assigned a respective weight.

15. The method of claim 14, 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.

16. The method of claim 9, 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 method of claim 15, 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.

18. A system for interactively constructing dictionaries that represent respective concepts usable for machine learning, the method comprising:

one more memory devices; and

one or more processors configured to;

generate an interface for editing a dictionary that represents a respective concept, wherein the dictionary represents the respective concept by including a list of words that are positive examples of the respective concept, and wherein the dictionary is usable as a feature for training a classifier;

present on the interface a positive-example input field configured to receive user-input words that are positive examples of the respective concept represented by the dictionary;

present on the user interface a negative-example input field configured to receive user-input words that are negative examples of the respective concept represented by the dictionary;

present on the user interface a suggestion-set field configured to display a system-generated list of suggested words, wherein the suggested words are examples of a generalized concept that is determined from words in one or both of the positive-example input field or the negative-example field;

receive one or more user-input words that are positive or negative examples of the respective concept represented by the dictionary, wherein the one or more user-input words are received from one or more of

a typed entry, or

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

determine a first generalized concept from the one or more user-input positive or negative examples;

based on the first generalized concept, generate a set of suggested words that are examples of the first generalized concept;

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

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

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

refine 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, wherein the refined set of suggested words represents a refined generalized concept;

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

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

save the contents of the positive-example input field, comprising the user-input words that are positive examples of the respective concept, in the dictionary that represents the respective concept, in the one or more memory devices.

19. The system of claim 18, the one or more processors further configured to:

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

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,

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,

a user selection that indicates whether word frequencies are normalized,

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

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 system 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.