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

• US 8,706,742 B1
• Filed: 01/03/2012
• Issued: 04/22/2014
• 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, Tal-Rothschild, Liad
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US13/342,770
• Time in Patent Office: 840 Days
• Field of Search: 707/722, 707/759, 707/749, 715/204, 715/234
• US Class Current: 707/749
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

A system including an electronic repository having a multiplicity of accesses to a respective multiplicity of electronic documents and metadata; a document rater using a processor to run a first computer algorithm on the multiplicity of electronic documents which yields a score which rates each of the multiplicity of electronic documents to an issue; and a metadata-based document discriminator to run a second computer algorithm on at least some of the metadata which yields leads, each lead having at least one metadata value for at least one metadata parameter, whose value correlates with the score of the electronic documents to the issue, typically used in combination with 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.

Claims

1. A system for computerized derivation of leads from a huge body of data, the system comprising:

an electronic repository including a multiplicity of accesses to a respective multiplicity of electronic documents and metadata including metadata parameters having metadata values characterizing each of said multiplicity of electronic documents;

a document rater using a processor to run a first computer algorithm on said multiplicity of electronic documents which yields a score which rates each of said multiplicity of electronic documents; and

a metadata-based document discriminator using the processor to run a second computer algorithm on at least some of said metadata which yields leads, each lead comprising at least one metadata value for at least one metadata parameter, whose value correlates with the score of said electronic documents,

wherein said discriminator is operative to perform the following for each of a multiplicity of logical conditions defined over the individual documents'"'"' metadata;

a. access a subset of said multiplicity of electronic documents wherein membership in said subset, of an individual document from among said multiplicity of electronic documents, is determined by whether or not a current logical condition defined over said individual documents'"'"' metadata, is true;

b. compute at least one first value, including a proportion of documents having a relevance score whose value is “

relevant”

, over at least one subset;

c. Provide a second value including a proportion of documents having a relevance score whose value is “

relevant”

from among all of said multiplicity of electronic documents; and

d. compare said first value to the second value, define said logical condition defined over said individual documents'"'"' metadata as a lead when said first and second values differ by at least a predetermined extent and generate an output indication of the lead.

2. The system according to claim 1 wherein at least one of said accesses includes an individual one of said multiplicity of electronic documents.

3. The system according to claim 1 wherein said document rater comprises a relevance rater using the first computer algorithm to yield a relevance score which rates relevance of each of said multiplicity of electronic documents to an issue.

4. The system according to claim 3 wherein said document discriminator comprises a metadata-based relevant-irrelevant document discriminator characterized in that said at least one metadata value correlates with relevance of said electronic documents to the issue.

5. The system according to claim 4 wherein said at least one metadata value for at least one metadata parameter comprises a logical combination of conditions according to which a plurality of metadata parameters respectively assume a plurality of metadata ranges each range including at least one metadata value, wherein said logical combination is characterized in that documents from among said multiplicity of documents which satisfy said condition, statistically tend to be relevant to the issue, more than documents from among said multiplicity of documents, which do not satisfy said condition.

6. The system according to claim 4 wherein said relevance rater generates binary relevance scores having exactly 2 values:

“

relevant” and

“

irrelevant”

, and wherein said metadata-based relevant-irrelevant document discriminator is operative for;

computing a first value, including a proportion of documents having a relevance score whose value is “

relevant”

, over a subset of said multiplicity of electronic documents wherein membership in said subset, of an individual document from among said multiplicity of electronic documents, is determined by whether or not a logical condition defined over said individual documents'"'"' metadata, is true; and

comparing said first value to a second value including a proportion of documents having a relevance score whose value is “

relevant”

from among all of said multiplicity of electronic documents and

if said first and second values differ by at least a predetermined extent, defining said logical condition defined over said individual documents'"'"' metadata as a lead and generating an output indication thereof.

7. The system according to claim 4 wherein said relevance rater generates binary relevance scores having exactly 2 values:

“

relevant” and

“

irrelevant” and

wherein said discriminator is operative to define as a lead, each logical condition over metadata which is statistically dependent, vis a vis possession by electronic documents of “

relevant” and

“

irrelevant”

scores, at a predetermined level of confidence.

8. The system according to claim 4 wherein said relevance rater comprises an electronic document analyzer 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 analyzer comprising:

iterative apparatus for performing a plurality of machine learning iterations on said N electronic documents wherein said iterations teach said iterative apparatus to determine relevance of documents to at least one issue in said set of issues; and

apparatus for determining at least one relevance determination quality criterion characterizing said iterative apparatus'"'"'s current performance.

9. The system according to claim 8, and also comprising iteration cost effectiveness analysis apparatus for estimating the cost effectiveness of continued use of said iterative apparatus on said at least N documents vs. termination of use of said iterative apparatus.

10. The system according to claim 9 wherein said cost effectiveness analysis apparatus includes apparatus for estimating at least one relevance determination quality criterion of said iterative apparatus'"'"'s future performance assuming continued use of said iterative apparatus.

11. The system according to claim 9 wherein said cost effectiveness analysis apparatus includes apparatus for computing a budget required to enable continued use of said iterative apparatus.

12. The system according to claim 11 wherein said budget is computed by computing a culling percentage.

13. The system according to claim 12 wherein said culling percentage is computed by:

generating a graph of a relevance determination quality criterion characterizing the iterative apparatus'"'"'s performance during an iteration as a function of a serial number of said iteration; and

computing an integral thereof.

14. The system according to claim 8 wherein said set of issues comprises a plurality of issues and also comprising a multi-issue manager operative to monitor the system'"'"'s analysis of relevance of said at least N documents to each of the plurality of issues and to prompt at least one of the user and the system if relevance has not been analyzed for some of said plurality of issues.

15. The system according to claim 4 wherein said relevance rater comprises an electronic document analyzer 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 analyzer comprising:

binary relevance determining apparatus for generating binary relevance data characterizing relevance of said documents to at least one issue in said set of issues, said binary relevance data being generated by applying a cut-off point to multi-value relevance data; and

cut-off point selection cost effectiveness analysis apparatus for estimating the relative cost effectiveness of a multiplicity of possible cut-off points.

16. The system according to claim 15 wherein said cut-off point selection cost effectiveness analysis apparatus comprises apparatus for generating a computer display of a continuum of possible cut-off points, each position along said continuum corresponding to a possible cut-off point, and apparatus for accepting a user'"'"'s indication of positions along said continuum and for computing and displaying, for each user-indicated position, cost effectiveness information characterizing the cut-off point corresponding to said user-indicated position.

17. The system according to claim 16 wherein said apparatus for accepting is operative to accept readings from a user input device sliding along said continuum and to display said cost effectiveness information for each individual user-indicated position along said continuum as said user input device slides onto said individual user-indicated position.

18. The system according to claim 16 wherein said binary relevance determining apparatus comprises iterative apparatus and wherein cost effectiveness information includes information regarding a budget required to enable continued use of said iterative apparatus.

19. The system according to claim 18 wherein said information regarding a budget comprises a culling percentage computed by:

generating a graph of a relevance determination quality criterion characterizing the iterative apparatus'"'"'s performance during an iteration as a function of a serial number of said iteration; and

computing an integral thereof.

20. The system according to claim 15 wherein said set of issues comprises a plurality of issues and also comprising a multi-issue manager operative to monitor the system'"'"'s analysis of relevance of said at least N documents to each of the plurality of issues and to prompt at least one of the user and the system if relevance has not been analyzed for some of said plurality of issues.

21. The system according to claim 4 wherein said relevance rater comprises an electronic document analyzer 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 analyzer comprising:

iterative binary relevance determining apparatus for iteratively generating binary relevance data characterizing relevance of said documents to at least one issue in said set of issues by performing machine learning on an iteration-specific training set of documents, said binary relevance data being generated by iteratively computing a cut-off point, wherein for at least one individual iteration, said iteration-specific training set is well distributed about the cut-off point as computed in said individual iteration.

22. The system according to claim 21 wherein for each individual iteration, said iteration-specific training set is well distributed about the cut-off point as computed in said individual iteration.

23. The system according to claim 21 wherein said set of issues comprises a plurality of issues and also comprising a multi-issue manager operative to monitor the system'"'"'s analysis of relevance of said at least N documents to each of the plurality of issues and to prompt at least one of the user and the system if relevance has not been analyzed for some of said plurality of issues.

24. The system according to claim 4 wherein said relevance rater comprises an electronic document analyzer 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 analyzer comprising:

iterative binary relevance determining apparatus for iteratively generating binary relevance data characterizing relevance of said documents to at least one issue in said set of issues by performing machine learning on an iteration-specific training set of documents; and

stability computation apparatus operative to monitor stability of said iterative binary relevance determining apparatus by using a first control group in order to estimate quality of relevance determination performed by said iterative binary relevance determining apparatus if iterations are continued vs. if iterations are terminated.

25. The system according to claim 24 wherein said set of issues comprises a plurality of issues and also comprising a multi-issue manager operative to monitor the system'"'"'s analysis of relevance of said at least N documents to each of the plurality of issues and to prompt at least one of the user and the system if relevance has not been analyzed for some of said plurality of issues.

26. The system according to claim 24 wherein said binary relevance data is generated by using a second control set of documents to select a cut-off point from among a plurality of possible cut-off points.

27. The system according to claim 26 wherein said first control set is identical to said second control set.

28. The system according to claim 1 wherein said at least one metadata value comprises at least one range of values for at least one metadata parameter for which it is true that documents from among said multiplicity of documents, for which said metadata parameter'"'"'s value falls within said range, statistically tend to be relevant to an issue, more than documents from among said multiplicity of documents, for which said metadata parameter'"'"'s value falls outside of said range.

29. The system according to claim 1 wherein said metadata-based document discriminator comprises Microsoft'"'"'s dsofile.dllm.

30. The system according to claim 1 wherein said electronic repository is generated by software having at least some Law-prediscovery software functionality.

31. The system according to claim 1 wherein said document rater comprises an electronic document analysis system comprising:

an electronic analyzer operative to generate a predetermined output characterizing a set of electronic documents; and

an electronic analyzer evaluation system operative to receive an additional output regarding said set of electronic documents whose additional output was generated by an external electronic document analysis system and to compare said predetermined output and said additional output in order to validate said electronic analyzer vis a vis said external electronic document analysis system.

32. The system according to claim 31 wherein said electronic analyzer evaluation system is operative to compare said predetermined output and said additional output on a document by document basis, thereby to determine difference values for at least some of said set of electronic documents, and to merge said difference values.

33. The system according to claim 1 wherein said document discriminator comprises a metadata-based relevant-irrelevant document discriminator characterized in that said at least one metadata value correlates with relevance of said electronic documents to an issue.

34. The system according to claim 1 wherein at least one of said accesses includes an indication of a location, in a data repository, of an individual one of said multiplicity of electronic documents.

35. The system according to claim 34 wherein said indication comprises a link.

36. The system according to claim 1 wherein said document rater generates binary relevance scores having exactly 2 levels, and wherein said metadata-based document discriminator is operative for:

computing a first value, including a proportion of documents having a first level, over a subset of said multiplicity of electronic documents wherein membership in said subset, of an individual document from among said multiplicity of electronic documents, is determined by whether or not a logical condition defined over said individual documents'"'"' metadata, is true; and

comparing said first value to a second value including a proportion of documents having a first level from among all of said multiplicity of electronic documents and, if said first and second values differ by at least a predetermined extent, defining said logical condition defined over said individual documents'"'"' metadata as a lead and generating an output indication thereof, if said first and second values differ by at least a predetermined extent.

37. The system according to claim 1 wherein said document rater generates binary relevance scores having exactly 2 levels and wherein said discriminator is operative to define as a lead, each logical condition over metadata which is statistically dependent, vis a vis belonging of electronic documents to the 2 levels, at a predetermined level of confidence.

38. A method for computerized derivation of leads from a huge body of data, the method comprising:

providing an electronic repository including a multiplicity of accesses to a respective multiplicity of electronic documents and metadata including metadata parameters having metadata values characterizing each of said multiplicity of electronic documents;

using a processor to rapidly run a first computer algorithm on said multiplicity of electronic documents which yields a score which rates each of said multiplicity of electronic documents; and

using the processor to rapidly run a second computer algorithm on at least some of said metadata which yields leads, each lead comprising at least one metadata value for at least one metadata parameter, whose value correlates with the score of said electronic documents,

including performing the following for each of a multiplicity of logical conditions defined over the individual documents'"'"' metadata;

a. access a subset of said multiplicity of electronic documents wherein membership in said subset, of an individual document from among said multiplicity of electronic documents, is determined by whether or not a current logical condition defined over said individual documents'"'"' metadata, is true;

b. compute at least one first value, including a proportion of documents having a relevance score whose value is “

relevant”

, over at least one subset;

c. Provide a second value including a proportion of documents having a relevance score whose value is “

relevant”

from among all of said multiplicity of electronic documents; and

d. compare said first value to the second value, define said logical condition defined over said individual documents'"'"' metadata as a lead when said first and second values differ by at least a predetermined extent and generate an output indication of the lead.

39. The method according to claim 38 wherein said steps are performed for each of a multiplicity of logical conditions defined over the individual documents'"'"' metadata.

40. The method according to claim 38 and also comprising generating an output indication of said leads.

41. The method according to claim 38 and also comprising conducting legal e-discovery based on said leads.

42. The method according to claim 38 wherein said using the processor to generate a score comprises an electronic document analysis process 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 process 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 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; and

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

43. The method according to claim 42 and wherein said process also comprises:

partitioning said at least N 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 documents thereby to generate a final output and generating a computer display of said final output.

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

45. The method according to claim 44 wherein said quality criterion comprises an F-measure.

46. The method according to claim 44 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.

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

48. The method according to claim 47 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.

49. The method according to claim 43 wherein said input comprises a user input received from a human user.

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

52. The method according to claim 43 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.

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

un-weighted F-measure;

weighted F-measure;

precision;

recall; and

accuracy.

54. The method according to claim 52 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.

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

56. The method according to claim 43 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.

57. The method according to claim 43 and also 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.

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

59. A method according to claim 42 and also comprising seeking an input as to whether or not to return to said receiving step thereby to initiate a new iteration I+1 including said receiving, building and running and initiating said new iteration I+1 if and only if so indicated by said input.

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

61. The method according to claim 42 wherein said using a processor to generate a relevance score comprises a process for electronic document analysis comprising:

using a text classifier to classify each document in a set of documents as relevant or irrelevant to an issue; and

generating a computer display of at least one user-selected document within said set of documents, wherein at least some words in said user-selected document are differentially presented depending on their contribution to said classification of the document as relevant or irrelevant by said text classifier.

62. The method according to claim 61 wherein said words differentially presented are differentially colored and wherein intensity of color is used to represent strength of said contribution for each word.

63. The method according to claim 61 and also comprising sequentially removing certain sets of words from each individual document in the set of documents 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.

64. The method according to claim 42 wherein said using a processor to generate a relevance score comprises an expert-based document analysis process comprising:

electronically finding near-duplicate documents from among a set of documents;

accepting an expert'"'"'s input regarding at least some of said set of documents; and

alerting the expert each time said expert'"'"'s input regarding any individual document differs from his verdict regarding at least one additional document which has been found by said electronically finding step to be a near duplicate of said individual document.

65. The method according to claim 42 and also comprising:

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

generating a computer display of at least one user-selected document within said N 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.

66. The method according to claim 65 wherein said words differentially presented are differentially colored and wherein intensity of color is used to represent strength of said contribution for each word.

67. The method according to claim 65 and also comprising 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.

68. The method according to claim 38 wherein said score comprises a relevance score which rates relevance of each of said multiplicity of electronic documents to an issue and wherein said metadata value correlates with the relevance of said electronic documents to the issue.

50. The method according to claim 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 documents.

69. A computer program product, comprising a tangible computer usable medium having a computer readable program code embodied therein, said computer readable program code adapted to be executed to implement a method for computerized derivation of leads from a huge body of data, the method comprising:

providing an electronic repository including a multiplicity of accesses to a respective multiplicity of electronic documents and metadata including metadata parameters having metadata values characterizing each of said multiplicity of electronic documents;

providing a relevance rater using a processor to provide, for each individual document from among said multiplicity of electronic documents, a relevance score which rates relevance of said individual document to at least one issue; and

providing a metadata-based relevant-irrelevant document discriminator using the processor to rapidly run a second computer algorithm on at least some of said metadata which yields leads, each lead comprising at least one metadata value for at least one metadata parameter, whose value correlates with relevance of said electronic documents to the issue,

wherein said discriminator is operative to perform the following for each of a multiplicity of logical conditions defined over the individual documents'"'"' metadata;

a. access a subset of said multiplicity of electronic documents wherein membership in said subset, of an individual document from among said multiplicity of electronic documents, is determined by whether or not a current logical condition defined over said individual documents'"'"' metadata, is true;

b. compute at least one first value, including a proportion of documents having a relevance score whose value is “

relevant”

, over at least one subset;

c. Provide a second value including a proportion of documents having a relevance score whose value is “

relevant”

from among all of said multiplicity of electronic documents; and

d. compare said first value to the second value, define said logical condition defined over said individual documents'"'"' metadata as a lead when said first and second values differ by at least a predetermined extent and generate an output indication of the lead.

70. The computer program product according to claim 69 wherein said relevance rater uses the processor to accumulate relevance scores from a human user.