Classifying documents using multiple classifiers

• US 9,104,972 B1
• Filed: 03/24/2014
• Issued: 08/11/2015
• Est. Priority Date: 03/13/2009
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Korolev, Dmitry, Maennel, Hartmut
• Primary Examiner(s): Arjomandi, Noosha
• Application Number:
  US14/223,632
• Time in Patent Office: 505 Days
• Field of Search: 707/705, 707/708, 707/713, 707/729, 707/731
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/048 Fuzzy inferencing

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for classifying resources using scores from multiple classifiers. In general, one aspect of the subject matter described in this specification can be embodied in methods that include the actions of receiving identifying a collection of documents to classify; receiving a plurality of classifiers for scoring a document with respect to a specified property; for each document in the collection, applying each of the plurality of classifiers, each classifier generating a score associated with a likelihood that the document has the specified property, combining the scores from each classifier including applying a multiple classifier model that uses monotonic regression to combine the plurality of classifiers, and classifying the document as having the specified property based on the combined score.

Claims

1. A computer-implemented method comprising:

computing multiple respective scores for each document in a collection of documents, one score from each of a plurality of D distinct classifiers, wherein each classifier computes a respective score representing a likelihood that the document has a property P, wherein each classifier has a respective lower threshold a_j, wherein documents having a score less than a_j are unlikely to have the property P, and wherein each classifier has a respective upper threshold b_j, wherein documents having a score greater than b_j are likely to have the property P;

determining, for each respective classifier, a plurality of intervals between a_j and b_j for the classifier;

determining, for each document in the collection of documents, a combination of intervals I₁¹ to I_D^K according to which interval of the plurality of intervals each respective score for the document belongs;

determining, for each combination of intervals I_j¹ to I_j^K, whether any documents in the collection of documents have a corresponding combination of intervals I₁¹ to I_D^K;

selecting no more than M documents for each combination of intervals I_j¹ to I_j^K for which at least one document in the collection has the corresponding combination of intervals; and

training a multiple classifier model for the D distinct classifiers using each selected document.

2. The method of claim 1, wherein determining, for each respective classifier, a plurality of intervals between a_j and b_j for the classifier comprises determining K intervals for each distinct classifier.

3. The method of claim 2, wherein selecting no more than M documents for each combination of intervals comprises selecting no more than N total documents, wherein N is an upper bound on a number of documents selected.

4. The method of claim 3, further comprising:

determining K such that K is the smallest integer that satisfies K^D>

=N.

5. The method of claim 4, further comprising:

determining, for each classifier, a middle score m_j, wherein determining a plurality of intervals between a_j and b_j for each classifier comprises determining K/2 intervals between a_j and m_j and K/2 intervals between m_j and b_j.

6. The method of claim 5, wherein determining, for each classifier, the middle score m_j comprises determining the middle score m_j such that a ratio of documents having a score greater than m_j is a ratio of documents having the property P.

7. The method of claim 1, wherein substantially half of the selected documents have the property P.

8. The method of claim 1, further comprising:

providing each selected document to one or more human raters; and

receiving, from the one or more human raters, an indication of whether or not each document has the property P.

9. The method of claim 1, wherein training the multiple classifier model comprises training a monotonic regression model.

10. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

computing multiple respective scores for each document in a collection of documents, one score from each of a plurality of D distinct classifiers, wherein each classifier computes a respective score representing a likelihood that the document has a property P, wherein each classifier has a respective lower threshold a_j, wherein documents having a score less than a_j are unlikely to have the property P, and wherein each classifier has a respective upper threshold b_j, wherein documents having a score greater than b_j are likely to have the property P;

determining, for each respective classifier, a plurality of intervals between a_j and b_j for the classifier;

determining, for each document in the collection of documents, a combination of intervals I₁¹ to I_D^K according to which interval of the plurality of intervals each respective score for the document belongs;

determining, for each combination of intervals I_j¹ to I_j^K, whether any documents in the collection of documents have a corresponding combination of intervals I₁¹ to I_D^K;

selecting no more than M documents for each combination of intervals I_j¹ to I_j^K for which at least one document in the collection has the corresponding combination of intervals; and

training a multiple classifier model for the D distinct classifiers using each selected document.

11. The system of claim 10, wherein determining, for each respective classifier, a plurality of intervals between a_j and b_j for the classifier comprises determining K intervals for each distinct classifier.

12. The system of claim 11, wherein selecting no more than M documents for each combination of intervals comprises selecting no more than N total documents, wherein N is an upper bound on a number of documents selected.

13. The system of claim 12, wherein the operations further comprise:

determining K such that K is the smallest integer that satisfies K^D>

=N.

14. The system of claim 13, wherein the operations further comprise:

determining, for each classifier, a middle score m_j, wherein determining a plurality of intervals between a_j and b_j for each classifier comprises determining K/2 intervals between a_j and m_j and K/2 intervals between m_j and b_j.

15. The system of claim 14, wherein determining, for each classifier, the middle score m_j comprises determining the middle score m_j such that a ratio of documents having a score greater than m_j is a ratio of documents having the property P.

16. The system of claim 10, wherein substantially half of the selected documents have the property P.

17. The system of claim 10, wherein the operations further comprise:

providing each selected document to one or more human raters; and

receiving, from the one or more human raters, an indication of whether or not each document has the property P.

18. The system of claim 10, wherein training the multiple classifier model comprises training a monotonic regression model.

19. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

computing multiple respective scores for each document in a collection of documents, one score from each of a plurality of D distinct classifiers, wherein each classifier computes a respective score representing a likelihood that the document has a property P, wherein each classifier has a respective lower threshold a_j, wherein documents having a score less than a_j are unlikely to have the property P, and wherein each classifier has a respective upper threshold b_j, wherein documents having a score greater than b_j are likely to have the property P;

determining, for each respective classifier, a plurality of intervals between a_j and b_j for the classifier;

determining, for each document in the collection of documents, a combination of intervals I₁¹ to I_D^K according to which interval of the plurality of intervals each respective score for the document belongs;

determining, for each combination of intervals to I_j¹ to I_j^K, whether any documents in the collection of documents have a corresponding combination of intervals I₁¹ to I_D^K;

selecting no more than M documents for each combination of intervals I_j¹ to I_j^K for which at least one document in the collection has the corresponding combination of intervals; and

training a multiple classifier model for the D distinct classifiers using each selected document.

20. The computer program product of claim 19, wherein determining, for each respective classifier, a plurality of intervals between aj and bj for the classifier comprises determining K intervals for each distinct classifier.