Systems and methods for classifying electronic information using advanced active learning techniques

• US 9,678,957 B2
• Filed: 07/22/2015
• Issued: 06/13/2017
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Gordon Villy Cormack, Maura Robin Grossman
• Original Assignee: Gordon Villy Cormack, Maura Robin Grossman
• Inventors: Cormack, Gordon Villy, Grossman, Maura Robin
• Primary Examiner(s): CHANG, LI WU
• Application Number:
  US14/806,029
• Publication Number:
  US 20150324451A1
• Time in Patent Office: 692 Days
• Field of Search: None
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Systems and methods for classifying electronic information or documents into a number of classes and subclasses are provided through an active learning algorithm. In certain embodiments, seed sets may be eliminated by merging relevance feedback and machine learning phases. In certain embodiments, the active learning algorithm forks a number of classification paths corresponding to predicted user coding decisions for a selected document. The active learning algorithm determines an order in which the documents of the collection may be processed and scored by the forked classification paths. Such document classification systems are easily scalable for large document collections, require less manpower and can be employed on a single computer, thus requiring fewer resources. Furthermore, the classification systems and methods described can be used for any pattern recognition or classification effort in a wide variety of fields.

Claims

1. An active learning system for classifying documents in a document collection as a member of one or more classes or subclasses, the system comprising:

a processor being adapted to;

select a document from the document collection;

calculate at least two predicted classifiers for at least one of the one or more classes or subclasses, each predicted classifier being calculated using a document information profile for the selected document, a current classifier associated with at least one of the one or more classes or subclasses, and a different coding decision selected from a set of possible user coding decisions to be received from a user, thereby resulting in a plurality of predicted classifiers each one corresponding to a different user coding decision;

determine a processing order for a subset of documents in the document collection that indicates an order in which the documents of the subset are to be scored;

for each one of the predicted classifiers, calculate a set of scores for one or more documents in the document collection, at least in part, according to the processing order, wherein each score is generated for a document by utilizing the corresponding predicted classifier and a document information profile of the document to be scored;

receive a user coding decision;

determine whether one or more stopping criteria have been met using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision, wherein determining whether one or more stopping criteria have been met includes selecting and presenting documents from the document collection to a user and calculating an estimate of system effectiveness using the user coding decisions for the selected documents;

so long as the one or more stopping criteria have not been met, select a further document from the document collection and repeat the steps of calculating predicted classifiers, determining a processing order, calculating a set of scores, and classifying a set of documents based on the selected further documents; and

in response to determining whether one or more stopping criteria have been met, classify a set of documents in the document collection into one or more of the one or more classes or subclasses using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision.

9. The system of claim 1, wherein the document is selected using uncertainty sampling.

10. The system of claim 1, wherein the selected document is identified by unsupervised learning techniques as not being similar to a previously selected document.

11. The system of claim 1, wherein the processor is further adapted to manage priority queues for ranking the one or more documents of the document collection.

15. The system of claim 1, wherein the system further comprises a display that is adapted to display one or more graphs indicating a tradeoff between recall and precision.

16. The system of claim 1, wherein the user coding decision indicates whether or not a document is relevant or non-relevant to more than one of the one or more classes or subclasses.

17. The system of claim 1, wherein the processor is further adapted to assess user performance or system performance by comparing the subset of the set of scores with user coding decisions.

18. The system of claim 1, wherein the processor comprises a plurality of processors.

19. The system of claim 18, wherein at least one processor of the plurality of processors is adapted to receive document information profiles over a network.

20. The system of claim 1, wherein a processing time for calculating the set of scores for each predicted classifier is allocated according to one or more confidence values.

21. The system of claim 20, wherein the one or more confidence values comprise a calculated score or rank in a priority queue.

22. The system of claim 1, wherein the number of documents in the processing order is determined by an estimated review time for the selected document.

2. An active learning system for classifying documents in a document collection as a member of one or more classes or subclasses, the system comprising:

a processor being adapted to;

select a document from the document collection;

calculate at least two predicted classifiers for at least one of the one or more classes or subclasses, each predicted classifier being calculated using a document information profile for the selected document, a current classifier associated with at least one of the one or more classes or subclasses, and a different coding decision selected from a set of possible user coding decisions to be received from a user, thereby resulting in a plurality of predicted classifiers each one corresponding to a different user coding decision;

determine a processing order for a subset of documents in the document collection that indicates an order in which the documents of the subset are to be scored;

for each one of the predicted classifiers, calculate a set of scores for one or more documents in the document collection, at least in part, according to the processing order, wherein each score is generated for a document by utilizing the corresponding predicted classifier and a document information profile of the document to be scored;

receive a user coding decision;

determine whether one or more stopping criteria have been met using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision, wherein determining whether one or more stopping criteria have been met includes calculating an estimate of the number of documents in the document collection that are relevant to one of the classes or subclasses by fitting the subset of the set of scores to a standard distribution and validating the estimate using a sequence of user coding decisions;

so long as the one or more stopping criteria have not been met, select a further document from the document collection and repeat the steps of calculating predicted classifiers, determining a processing order, calculating a set of scores, and classifying a set of documents based on the selected further documents; and

in response to determining whether one or more stopping criteria have been met, classify a set of documents in the document collection into one or more of the one or more classes or subclasses using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision.

3. The system of claim 2, wherein the processing order is determined, at least in part, by a technique used to select the further document.

4. An active learning system for classifying documents in a document collection as a member of one or more classes or subclasses, the system comprising:

a processor being adapted to;

receive or provide relevance rankings, wherein the relevance rankings are generated by one or more keyword searching algorithms or by a comparison with one or more exemplary documents;

select a document from the document collection;

calculate at least two predicted classifiers for at least one of the one or more classes or subclasses, each predicted classifier being calculated using a document information profile for the selected document, a current classifier associated with at least one of the one or more classes or subclasses, and a different coding decision selected from a set of possible user coding decisions to be received from a user, thereby resulting in a plurality of predicted classifiers each one corresponding to a different user coding decision;

determine a processing order for a subset of documents in the document collection that indicates an order in which the documents of the subset are to be scored, wherein the processing order is derived, at least in part, from a set of scores calculated using the current classifier and the relevance rankings;

for each one of the predicted classifiers, calculate a set of scores for one or more documents in the document collection, at least in part, according to the processing order, wherein each score is generated for a document by utilizing the corresponding predicted classifier and a document information profile of the document to be scored; and

in response to receiving a user coding decision, classify a set of documents in the document collection into one or more of the one or more classes or subclasses using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision.

5. The system of claim 4, wherein the document is selected by choosing between utilizing the set of scores calculated using a current classifier, the relevance rankings or a combination of the set of scores calculated using a current classifier and the relevance rankings.

6. The system of claim 4, wherein the processor is further adapted to manage priority queues for ranking the one or more documents of the document collection.

7. The system of claim 6, wherein the ranking of the priority queues is derived from the subset of the set of scores and the relevance rankings.

8. The system of claim 6, wherein the processor is further adapted to select the document as one whose score or priority queue ranking is not within a range of scores or rankings associated with a previously selected document.

12. An active learning system for classifying documents in a document collection as a member of one or more classes or subclasses, the system comprising:

a processor being adapted to;

pre-process documents from the document collection to reduce the dimensionality of document information profiles, wherein pre-processing the documents includes converting characters of the document to a common case or compressing strings of non-alphanumeric characters to a single character;

select a document from the document collection;

calculate at least two predicted classifiers for at least one of the one or more classes or subclasses, each predicted classifier being calculated using a document information profile for the selected document, a current classifier associated with at least one of the one or more classes or subclasses, and a different coding decision selected from a set of possible user coding decisions to be received from a user, thereby resulting in a plurality of predicted classifiers each one corresponding to a different user coding decision;

determine a processing order for a subset of documents in the document collection that indicates an order in which the documents of the subset are to be scored;

for each one of the predicted classifiers, calculate a set of scores for one or more documents in the document collection, at least in part, according to the processing order, wherein each score is generated for a document by utilizing the corresponding predicted classifier and a document information profile of the document to be scored; and

in response to receiving a user coding decision, classify a set of documents in the document collection into one or more of the one or more classes or subclasses using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision.

13. An active learning for classifying documents in a document collection as a member of one or more classes or subclasses, the system comprising:

a processor being adapted to;

extract document information profiles from the documents in the document collection using an N-gram technique and hash N-grams to reduce dimensionalities of document information profiles, wherein the N-grams are hashed to balance frequencies of N-grams assigned to hash values;

select a document from the document collection;

calculate at least two predicted classifiers for at least one of the one or more classes or subclasses, each predicted classifier being calculated using a document information profile for the selected document, a current classifier associated with at least one of the one or more classes or subclasses, and a different coding decision selected from a set of possible user coding decisions to be received from a user, thereby resulting in a plurality of predicted classifiers each one corresponding to a different user coding decision;

determine a processing order for a subset of documents in the document collection that indicates an order in which the documents of the subset are to be scored;

for each one of the predicted classifiers, calculate a set of scores for one or more documents in the document collection, at least in part, according to the processing order, wherein each score is generated for a document by utilizing the corresponding predicted classifier and a document information profile of the document to be scored; and

in response to receiving a user coding decision, classify a set of documents in the document collection into one or more of the one or more classes or subclasses using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision.

14. The system of claim 13, wherein N-grams having a frequency above a predetermined threshold are ignored.

23. A non-transitory computer storage medium comprising program instructions for classifying documents in a document collection as a member of one or more classes or subclasses, wherein the program instructions, when executed on a processor, cause the processor to:

select a document from the document collection;

calculate at least two predicted classifiers for at least one of the one or more classes or subclasses, each predicted classifier being calculated using a document information profile for the selected document, a current classifier associated with at least one of the one or more classes or subclasses, and a different coding decision selected from a set of possible user coding decisions to be received from a user, thereby resulting in a plurality of predicted classifiers each one corresponding to a different user coding decision;

determine a processing order for a subset of documents in the document collection that indicates an order in which the documents of the subset are to be scored;

for each one of the predicted classifiers, calculate a set of scores for one or more documents in the document collection, at least in part, according to the processing order, wherein each score is generated for a document by utilizing the corresponding predicted classifier and a document information profile of the document to be scored;

receive a user coding decision;

determine whether one or more stopping criteria have been met using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision, wherein determining whether one or more stopping criteria have been met includes selecting and presenting documents from the document collection to a user and calculating an estimate of system effectiveness using the user coding decisions for the selected documents;

so long as the one or more stopping criteria have not been met, select a further document from the document collection and repeat the steps of calculating predicted classifiers, determining a processing order, calculating a set of scores, and classifying a set of documents based on the selected further documents; and

in response to determining whether one or more stopping criteria have been met, classify a set of documents in the document collection into one or more of the one or more classes or subclasses using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision.

24. The computer storage medium of claim 23, further comprising an operating system.

25. The computer storage medium of claim 24, wherein the program instructions are executed by the processor without requiring a user or an automated process to first copy the program instructions to a second computer storage medium as part of an installation procedure.

26. A method for classifying documents in a document collection as a member of one or more classes or subclasses, the method comprising:

selecting a document from the document collection;

calculating at least two predicted classifiers for at least one of the one or more classes or subclasses, each predicted classifier being calculated using a document information profile for the selected document, a current classifier associated with at least one of the one or more classes or subclasses, and a different coding decision selected from a set of possible user coding decisions to be received from a user, thereby resulting in a plurality of predicted classifiers each one corresponding to a different user coding decision;

determining a processing order for a subset of documents in the document collection that indicates an order in which the documents of the subset are to be scored;

for each one of the predicted classifiers, calculating a set of scores for one or more documents in the document collection, at least in part, according to the processing order, wherein each score is generated for a document by utilizing the corresponding predicted classifier and a document information profile of the document to be scored;

receiving a user coding decision;

determining whether one or more stopping criteria have been met using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision, wherein determining whether one or more stopping criteria have been met includes calculating an estimate of the number of documents in the document collection that are relevant to one of the classes or subclasses by fitting the subset of the set of scores to a standard distribution and validating the estimate using a sequence of user coding decisions;

so long as the one or more stopping criteria have not been met, selecting a further document from the document collection and repeating the steps of calculating predicted classifiers, determining a processing order, calculating a set of scores, and classifying a set of documents based on the selected further documents; and

in response to determining whether one or more stopping criteria have been met, classifying a set of documents in the document collection into one or more of the one or more classes or subclasses using a subset of the set of scores based on the predicted classifier that corresponds to the received user coding decision.

27. A method for processing documents in a document collection using a continuous active learning algorithm, the method comprising:

generating or receiving a document information profile for one or more of the documents in the document collection, each document information profile corresponding to a particular document and representing features of that document;

selecting a first document from the document collection to present to a human reviewer;

receiving a user coding decision associated with the first document;

calculating a classifier based on the received user coding decision associated with the first document and the document information profile for the first document;

computing a first set of scores for a subset of documents in the collection by applying the classifier to the document information profile for each document in the subset for which the first set of scores are computed;

determining a first plurality of rankings for documents in the document collection by choosing between the first set of scores, relevance rankings derived from user input for the documents in the document collection or a combination of the first set of scores and the relevance rankings;

selecting a further document from the document collection to present to a human reviewer based on the first plurality of rankings;

receiving a user coding decision associated with the further document;

updating the classifier based on the received user coding decision associated with the further document and the document information profile for the further document;

computing a second set of scores for a subset of documents in the collection by applying the updated classifier to the document information profile for each document in the subset for which the second set of scores are computed;

determining a second plurality of rankings for documents in the document collection by choosing between the second set of scores, relevance rankings derived from user input for the documents in the document collection or a combination of the second set of scores and the relevance rankings;

determining whether a stopping criterion is met based on the user coding decisions associated with the further document or based on one or more thresholds set using the computed second set of scores; and

in response to determining that the stopping criterion has not been met, repeating the steps of selecting a further document, receiving a user coding decision associated with the further document, updating the classifier, computing a second set of scores, determining a second plurality of rankings, and determining whether a stopping criterion is met.

28. The method of claim 27, wherein the user coding decision indicates whether or not a document is relevant or non-relevant to a class or subclass.

29. The method of claim 27, wherein calculating or updating the at least one classifier further comprises calculating or updating a plurality of classifiers each corresponding to one of a plurality of classes or subclasses.

30. The method of claim 27, wherein the first or second set of scores comprises scores computed for all of the documents in the document collection.

31. The method of claim 27, wherein the relevance rankings are generated by one or more keyword searching algorithms or by a comparison with one or more exemplary documents.

32. The method of claim 27, wherein the further document is selected using uncertainty sampling.

33. The method of claim 27, wherein the further document is selected as one whose score or ranking is not within a range of scores or rankings associated with a previously selected document.

34. The method of claim 27, wherein the selected further document is identified by unsupervised learning techniques as not being similar to a previously selected document.

35. The method of claim 27, wherein selecting a further document comprises choosing among a set of techniques for selecting the further document.

36. The method of claim 35, wherein the choosing among the set of techniques is prioritized using move-to-front pooling.

37. The method of claim 27, wherein the classifier is updated using the equation

38. The method of claim 27, wherein document information profiles are generated using an N-gram technique.

39. The method of claim 27, wherein the one or more thresholds are set by selecting documents for review to estimate at least one of precision, recall, false positive rate, false negative rate, true negative rate, and true positive rate.

40. The method of claim 27, wherein determining whether a stopping criterion is met based on the user coding decisions further comprises:

calculating an estimate of the number of documents in the document collection that are relevant to a class or subclass by fitting calculated scores to a standard distribution; and

validating the estimate using a sequence of user coding decisions.

41. The method of claim 40, wherein the standard distribution is a Gaussian distribution.

42. The method of claim 27, wherein the one or more thresholds are set by calculating one or more provisional thresholds for classification and comparing classification results with user coding decisions for a control set of documents, wherein the classification results are determined by comparing a computed set of scores with the one or more provisional thresholds.

43. The method of claim 27, wherein each document information profile comprises a numerical vector.

44. The method of claim 27, further comprising classifying a set of documents in the document collection into one or more classes or subclasses based on a computed set of scores.

45. The method of claim 27, wherein the documents in the collection are processed for the purpose of conducting e-discovery in legal proceedings.

46. A continuous active learning system for processing documents in a document collection the system comprising:

a processor being adapted to;

generate or receive a document information profile for one or more of the documents in the document collection, each document information profile corresponding to a particular document and representing features of that document;

select a first document from the document collection to present to a human reviewer;

receive a user coding decision associated with the first document;

calculate a classifier based on the received user coding decision associated with the first document and the document information profile for the first document;

compute a first set of scores for a subset of documents in the collection by applying the classifier to the document information profile for each document in the subset for which the first set of scores are computed;

determine a first plurality of rankings for documents in the document collection by choosing between the first set of scores, relevance rankings derived from user input for the documents in the document collection or a combination of the first set of scores and the relevance rankings;

select a further document from the document collection to present to a human reviewer based on the first plurality of rankings;

receive a user coding decision associated with the further document;

update the classifier based on the received user coding decision associated with the further document and the document information profile for the further document;

compute a second set of scores for a subset of documents in the collection by applying the updated classifier to the document information profile for each document in the subset for which the second set of scores are computed;

determine a second plurality of rankings for documents in the document collection by choosing between the second set of scores, relevance rankings derived from user input for the documents in the document collection or a combination of the second set of scores and the relevance rankings;

determine whether a stopping criterion is met based on the user coding decisions associated with the further document or based on one or more thresholds set using the computed second set of scores; and

in response to determining that the stopping criterion has not been met, repeat the steps of selecting a further document, receiving a user coding decision associated with the further document, updating the classifier, computing a second set of scores, determining a second plurality of rankings, and determining whether a stopping criterion is met.

47. A non-transitory computer storage medium comprising program instructions for processing documents in a document collection using a continuous active learning algorithm, wherein the program instructions, when executed on a processor, cause the processor to:

generate or receive a document information profile for one or more of the documents in the document collection, each document information profile corresponding to a particular document and representing features of that document;

select a first document from the document collection to present to a human reviewer;

calculate a classifier based on a received user coding decision associated with the first document and the document information profile for the first document;

compute a first set of scores for a subset of documents in the collection by applying the classifier to the document information profile for each document in the subset for which the first set of scores are computed;

determine a first plurality of rankings for documents in the document collection by choosing between the first set of scores, relevance rankings derived from user input for the documents in the document collection or a combination of the first set of scores and the relevance rankings;

select a further document from the document collection to present to a human reviewer based on the first plurality of rankings;

update the classifier based on a received user coding decision associated with the further document and the document information profile for the further document;

compute a second set of scores for a subset of documents in the collection by applying the updated classifier to the document information profile for each document in the subset for which the second set of scores are computed;

determine a second plurality of rankings for documents in the document collection by choosing between the second set of scores, relevance rankings derived from user input for the documents in the document collection or a combination of the second set of scores and the relevance rankings;

determine whether a stopping criterion is met based on the user coding decisions associated with the further document or based on one or more thresholds set using the computed second set of scores; and

in response to determining that the stopping criterion has not been met, repeat the steps of selecting a further document, receiving a user coding decision associated with the further document, updating the classifier, computing a second set of scores, determining a second plurality of rankings, and determining whether a stopping criterion is met.