System for enhancing expert-based computerized analysis of a set of digital documents and methods useful in conjunction therewith

• US 8,527,523 B1
• Filed: 09/14/2009
• Issued: 09/03/2013
• Est. Priority Date: 04/22/2009
• Status: Active Grant

• Current Assignee: Microsoft Israel Research And Development (2002) Ltd (Microsoft Corporation)
• Original Assignee: Equivio Ltd. (Microsoft Corporation)
• Inventors: Ravid, Yiftach
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US12/559,173
• Time in Patent Office: 1,450 Days
• Field of Search: 707/749, 707/728, 358/448, 706/15, 706/54
• US Class Current: 707/749
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

An electronic document analysis method receiving N electronic documents pertaining to a case encompassing a set of issues including at least one issue and establishing relevance of at least the N documents to at least one individual issue in the set of issues, the method comprising, for at least one individual issue from among the set of issues, receiving an output of a categorization process applied to each document in training and control subsets of the at least N documents, the output including, for each document in the subsets, one of a relevant-to-the-individual issue indication and a non-relevant-to-the-individual issue indication; building a text classifier simulating the categorization process using the output for all documents in the training subset of documents; and running the text classifier on the at least N documents thereby to obtain a ranking of the extent of relevance of each of the at least N documents to the individual issue. The method may also comprise evaluating the text classifier'"'"'s quality using the output for all documents in the control subset.

Claims

1. An electronic document analysis method receiving N electronic documents pertaining to a case encompassing a set of issues including at least one issue and establishing relevance of at least the N electronic documents to at least one individual issue in the set of issues, the method comprising, for at least one individual issue from among said set of issues:

receiving an output of a categorization process applied to each document in training and control subsets of said at least N electronic documents, said output including, for each document in said subsets, one of a relevant-to-said-individual issue indication and a non-relevant-to-said-individual issue indication;

building a text classifier simulating said categorization process using said output for all documents in said training subset of documents;

evaluating said text classifier'"'"'s quality using said output for all documents in said control subset;

running the text classifier on the at least N electronic documents thereby to obtain a ranking of the extent of relevance of each of said at least N electronic documents to said individual issue;

partitioning said at least N electronic documents into uniformly ranked subsets of documents, said uniformly ranked subsets differing in ranking of their member documents by said text classifier and adding more documents from each of said uniformly ranked subsets to said training subset;

selecting a cut-off point for binarizing said rankings of said documents in said control subset;

using said cut-off point, computing and storing at least one quality criterion characterizing said binarizing of said rankings of said documents in said control subset, thereby to define a quality of performance indication of a current iteration I;

displaying a comparison of the quality of performance indication of the current iteration I to quality of performance indications of previous iterations;

seeking an input as to whether or, not to return to said receiving step thereby to initiate a new iteration I+1 which comprises said receiving, building, running, partitioning, selecting, and computing/storing steps and initiating said new iteration I+1 if and only if so indicated by said input; and

running the text classifier most recently built on at least said N electronic documents thereby to generate a final output and generating a computer display of said final output.

2. The method according to claim 1 wherein said cut-off point is selected from all ranks of documents in said control subset so as to maximize a quality criterion.

3. The method according to claim 2 wherein said quality criterion comprises an F-measure.

4. The method according to claim 2 wherein said at least one quality criterion characterizing said binarizing of said rankings of said documents in said control subset comprises at least one of the following criteria:

an F-measure;

a precision parameter, and a recall parameter.

5. The method according to claim 1 wherein said displaying a comparison comprises generating at least one graph of at least one quality criterion vs. iteration serial number.

6. The method according to claim 5 wherein said input comprises a computerized input including a computerized indication of flatness of said graph of at least one quality criterion vs. iteration serial number.

7. The method according to claim 1 wherein said input comprises a user input received from a human user.

8. The method according to claim 1 wherein said iteration I+1 uses a control subset larger than the control subset of iteration I, said control subset including the control subset of iteration I merged with an additional group of documents of pre-determined size randomly selected from said at least N electronic documents.

9. The method according to claim 1 wherein said computer display of said final output comprises a histogram of ranks for each issue.

10. The method according to claim 1 wherein said computer display of said final output comprises a function of an indication of a quality measure for each of a plurality of cut-off points.

11. The method according to claim 10 wherein said quality measure is selected from the following group:

un-weighted F-measure;

weighted F-measure;

precision;

recall; and

accuracy.

12. The method according to claim 10 wherein said function of said indication of a quality measure for each of a plurality of cut-off points comprises a graph of said quality measure as a function of cut-off point.

13. The method according to claim 12 wherein said function of said indication comprises a culling percentage including an integral of said graph.

14. The method according to claim 12 wherein said function of said indication comprises a culling percentage including an integral of said graph.

15. The method according to claim 1 wherein said set of issues comprises a plurality of issues and said computer display includes an indication of documents relevant to a logical combination of a plurality of issues.

16. The method according to claim 1 further comprising using said text classifier most recently built to generate, for at least one individual issue in said set of issues, a set of keywords differentiating documents relevant to said individual issue to documents irrelevant to said individual issue.

17. The method according to claim 1 wherein said receiving comprises receiving an output of a categorization process performed by a human operator.

18. The method according to claim 1 wherein said input is a function of at least one of a precision value, a recall value and an F-measure currently characterizing said classifier.

19. The method according to claim 1 further comprising:

classifying each document from among said N electronic documents as relevant or irrelevant to an issue; and

generating a computer display of at least one user-selected document within said N electronic documents, wherein at least some words in said user-selected document are differentially presented depending on their contribution to said classifying of the document as relevant or irrelevant, wherein

said words differentially presented are differentially colored and intensity of color is used to represent strength of said contribution for each word.

20. The method according to claim 1, further comprising:

classifying each document from anion said N electronic documents as relevant or irrelevant to an issue;

generating a computer display of at least one user-selected document within said N electronic documents, wherein at least some words in said user-selected, document are differentially presented depending on their contribution to said classifying of the document as relevant or irrelevant;

sequentially removing certain sets of words from each individual document classified and using the text classifier to classify said document'"'"'s relevance assuming said words are removed, thereby to obtain a relevance output for each set of words; and

comparing said relevance output to an output obtained by using the text classifier to classify said individual document without removing any words, thereby to obtain an indication of the contribution of each set of words to the relevance of the document.

21. The method according to claim 20 wherein said receiving comprises receiving an output of a categorization process performed by a human operator.

22. The method according to claim 20 wherein said cut-off point is selected from all ranks of documents in said control subset so as to maximize a quality criterion.

23. The method according to claim 22 wherein said quality criterion comprises an F-measure.

24. The method according to claim 22 wherein said at least one quality criterion characterizing said binarizing of said rankings of said documents in said control subset comprises at least one of the following criteria:

an F-measure;

a precision parameter, and a recall parameter.

25. The method according to claim 20 wherein said displaying a comparison comprises generating at least one graph of at least one quality criterion vs. iteration serial number.

26. The method according to claim 25 wherein said input comprises a computerized input including a computerized indication of flatness of said graph of at least one quality criterion vs. iteration serial number.

27. The method according to claim 20 wherein said input comprises a user input received from a human user.

28. The method according to claim 20 wherein said iteration I+1 uses a control subset larger than the control subset of iteration I, said control subset including the control subset of iteration I merged with an additional group of documents of pre-determined size randomly selected from said at least N electronic documents.

29. The method according to claim 20 wherein said computer display of said final output comprises a histogram of ranks for each issue.

30. The method according to claim 20 wherein said computer display of said final output comprises a function of an indication of a quality measure for each of a plurality of cut-off points.

31. The method according to claim 30 wherein said quality measure is selected from the following group:

un-weighted F-measure;

weighted F-measure;

precision;

recall; and

accuracy.

32. The method according to claim 30 wherein said function of said indication of a quality measure for each of a plurality of cut-off points comprises a graph of said quality measure as a function of cut-off point.

33. The method according to claim 32 wherein said function of said indication comprises a culling percentage including an integral of said graph.

34. The method according to claim 20 wherein said set of issues comprises a plurality of issues and said computer display includes an indication of documents relevant to a logical combination of a plurality of issues.

35. The method according to claim 20 further comprising using said text classifier most recently built to generate, for at least one individual issue in said set of issues, a set of keywords differentiating documents relevant to said individual issue to documents irrelevant to said individual issue.

36. The method according to claim 20 further comprising:

classifying each document from among said N electronic documents as relevant or irrelevant to an issue; and

generating a computer display of at least one user-selected document within said N electronic documents, wherein at least some words in said user-selected document are differentially presented depending on their contribution to said classifying of the document as relevant or irrelevant,

wherein said words differentially presented are differentially colored and wherein intensity of color is used to represent strength of said contribution for each word.

37. The method according to claim 20 wherein said input is a function of at least one of a precision value, recall value and F-measure currently characterizing said classifier.

38. The method according to claim 20 wherein said receiving comprises receiving an output of a categorization process performed by a human operator.

39. The method according to claim 20 wherein said cut-off point is selected from all ranks of documents in said control subset so as to maximize a quality criterion.

40. The method according to claim 39 wherein said quality criterion comprises an F-measure.

41. The method according to claim 39 wherein said at least one quality criterion characterizing said binarizing of said rankings of said documents in said control subset comprises at least one of the following criteria:

an F-measure;

a precision parameter, and a recall parameter.

42. The method according to claim 20 wherein said displaying a comparison comprises generating at least one graph of at least one quality criterion vs. iteration serial number.

43. The method according to claim 42 wherein said input comprises a computerized input including a computerized indication of flatness of said graph of at least one quality criterion vs. iteration serial number.

44. The method according to claim 20 wherein said input comprises a user input received from a human user.

45. The method according to claim 20 wherein said iteration I+1 uses a control subset larger than the control subset of iteration I, said control subset including the control subset of iteration I merged with an additional group of documents of pre-determined size randomly selected from said at least N electronic documents.

46. The method according to claim 20 wherein said computer display of said final output comprises a histogram of ranks for each issue.

47. The method according to claim 20 wherein said computer display of said final output comprises a function of an indication of a quality measure for each of a plurality of cut-off points.

48. The method according to claim 47 wherein said quality measure is selected from the following group:

un-weighted F-measure;

weighted F-measure;

precision;

recall; and

accuracy.

49. The method according to claim 47 wherein said function of said indication of a quality measure for each of a plurality of cut-off points comprises a graph of said quality measure as a function of cut-off point.

50. The method according to claim 20 wherein said set of issues comprises a plurality of issues and said computer display includes an indication of documents relevant to a logical combination of a plurality of issues.

51. The method according to claim 20 further comprising using said text classifier most recently built to generate, for at least one individual issue in said set of issues, a set of keywords differentiating documents relevant to said individual issue to documents irrelevant to said individual issue.

52. The method according to claim 20 further comprising:

classifying each document from among said N electronic documents as relevant or irrelevant to an issue; and

generating a computer display of at least one user-selected document within said N electronic documents, wherein at least some words in said user-selected document are differentially presented depending on their contribution to said classifying of the document as relevant or irrelevant,

wherein said words differentially presented are differentially colored and wherein intensity of color is used to represent strength of said contribution for each word.

53. The method according to claim 19 wherein said receiving comprises receiving an output of a categorization process performed by a human operator.

54. The method according to claim 19 wherein said cut-off point is selected from all ranks of documents in said control subset so as to maximize a quality criterion.

55. The method according to claim 54 wherein said quality criterion comprises an F-measure.

56. The method according to claim 54 wherein said at least one quality criterion characterizing said binarizing of said rankings of said documents in said control subset comprises at least one of the following criteria:

an F-measure;

a precision parameter, and a recall parameter.

57. The method according to claim 19 wherein said displaying a comparison comprises generating at least one graph of at least one quality criterion vs. iteration serial number.

58. The method according to claim 57 wherein said input comprises a computerized input including a computerized indication of flatness of said graph of at least one quality criterion vs. iteration serial number.

59. The method according to claim 19 wherein said input comprises a user input received from a human user.

60. The method according to claim 19 wherein said iteration I+1 uses a control subset larger than the control subset of iteration I, said control subset including the control subset of iteration I merged with an additional group of documents of pre-determined size randomly selected from said at least N electronic documents.

61. The method according to claim 19 wherein said computer display of said final output comprises a histogram of ranks for each issue.

62. The method according to claim 19 wherein said computer display of said final output comprises a function of an indication of a quality measure for each of a plurality of cut-off points.

63. The method according to claim 62 wherein said quality measure is selected from the following group:

un-weighted F-measure;

weighted F-measure;

precision;

recall; and

accuracy.

64. The method according to claim 62 wherein said function of said indication of a quality measure for each of a plurality of cut-off points comprises a graph of said quality measure as a function of cut-off point.

65. The method according to claim 64 wherein said function of said indication comprises a culling percentage including an integral of said graph.

66. The method according to claim 19 wherein said set of issues comprises a plurality of issues and said computer display includes an indication of documents relevant to a logical combination of a plurality of issues.

67. The method according to claim 19 further comprising using said text classifier most recently built to generate, for at least one individual issue in said set of issues, a set of keywords differentiating documents relevant to said individual issue to documents irrelevant to said individual issue.

68. The method according to claim 19 wherein said input is a function of at least one of a precision value, a recall value and an F-measure currently characterizing said classifier.