Apparatus, method and computer-accessible medium for explaining classifications of documents

• US 9,836,455 B2
• Filed: 02/23/2012
• Issued: 12/05/2017
• Est. Priority Date: 02/23/2011
• Status: Expired due to Fees

• Current Assignee: New York University
• Original Assignee: New York University, University Of Antwerp
• Inventors: Martens, David, Provost, Foster
• Primary Examiner(s): Spooner, Lamont
• Application Number:
  US14/001,242
• Publication Number:
  US 20140229164A1
• Time in Patent Office: 2,112 Days
• Field of Search: 704 1, 704 9, 704 10
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

Classification of collections of items such as words, which are called “document classification,” and more specifically explaining a classification of a document, such as a web-page or website. This can include exemplary procedure, system and/or computer-accessible medium to find explanations, as well as a framework to assess the procedure'"'"'s performance. An explanation is defined as a set of words (e.g., terms, more generally) such that removing words within this set from the document changes the predicted class from the class of interest. The exemplary procedure system and/or computer-accessible medium can include a classification of web pages as containing adult content, e.g., to allow advertising on safe web pages only. The explanations can be concise and document-specific, and provide insight into the reasons for the classification decisions, into the workings of the classification models, and into the business application itself. Other exemplary aspects describe how explaining documents'"'"' classifications can assist in improving the data quality and model performance.

Claims

1. A non-transitory computer readable medium including instructions thereon that are accessible by a hardware processing arrangement, wherein, when the processing arrangement executes the instructions, the processing arrangement is configured to generate information associated with at least one first classification of at least one document, comprising:

(a) identifying at least one characteristic of the at least one document, wherein the at least one characteristic includes a plurality of items;

(b) obtaining at least one second classification of the at least one document based on the at least one characteristic of the at least one document;

(c) removing at least one of the items from the at least one document;

(d) obtaining the at least one first classification based on the removal of the at least one of the items; and

(e) generating the information associated with the at least one first classification of the at least one document by repeating procedures (c) and (d) until the at least one first classification is different from the at least one second classification.

2. The non-transitory computer readable medium of claim 1, wherein the items include at least one of a (i) a plurality of words, (ii) a combination of words, (iii) at least one Uniform Resource Locator, or (iv) at least one locations visited by at least one device.

3. The non-transitory computer readable medium of claim 2, wherein the at least one characteristic includes a plurality of words, and wherein the processing arrangement is further configured to generate the information by removing at least one of the words when performing procedures (c) and (d).

4. The non-transitory computer readable medium of claim 3, wherein the at least one characteristic further includes a combination of words, and wherein the processing arrangement is further configured to generate the information by removing each word and every combination of words from the at least one document when performing procedures (c) and (d).

5. The non-transitory computer readable medium of claim 4, wherein the processing arrangement is further configured to omit at least some of the words or at least some combination of words when performing procedures (c) and (d).

6. The non-transitory computer readable medium of claim 5, wherein the processing arrangement is further configured to omit at least some of the words or at least some combination of words based on at least one of a pruning heuristic search or a hill climbing search.

7. The non-transitory computer readable medium of claim 1, wherein the information includes a minimum-size explanation.

8. The non-transitory computer readable medium of claim 1, wherein the information includes a plurality of minimum explanations.

9. The computer readable medium of claim 1, wherein the obtaining of the at least one second classification includes determining the at least one second classification of the at least one document based on the at least one characteristic of the at least one document.

10. A non-transitory computer readable medium including instructions thereon that are accessible by a hardware processing arrangement, wherein, when the processing arrangement executes the instructions, the processing arrangement is configured to generate information associated with at least one first classification of a collection, comprising:

(a) identifying at least one characteristic of the collection, wherein the at least one characteristic includes a plurality of items;

(b) obtaining at least one second classification of the collection based on the at least one characteristic of the collection;

(c) removing at least one of the items from the at least one document;

(d) obtaining the at least one first classification based on the removal of the at least one of the items; and

(e) generating the information associated with the at least one first classification of the collection by repeating procedures (c) and (d) until the at least one first classification is different than the at least one second classification.

11. The non-transitory computer readable medium of claim 10, wherein the information includes at least one of an explanation or a hyper-explanation of the at least one first classification of the collection, and wherein the at least one first classification is one of a plurality of classifications.

12. The non-transitory computer readable medium of claim 11, wherein the at least one of the explanation or the hyper-explanation is absent evidence indicating any of the at least one first classification and the at least one second classification.

13. The non-transitory computer readable medium of claim 12, wherein the at least one of the explanation or the hyper-explanation includes an indication of insufficient vocabulary.

14. The non-transitory computer readable medium of claim 11, wherein the at least one of the explanation or the hyper-explanation includes evidence exclusively indicating at least one of a negative classification or a default classification.

15. The non-transitory computer readable medium of claim 14, wherein the at least one of the explanation or the hyper-explanation is absent evidence of a positive classification.

16. The non-transitory computer readable medium of claim 11, wherein the at least one of the explanation or the hyper-explanation includes evidence exclusively indicating a positive classification.

17. The non-transitory computer readable medium of claim 16, wherein the at least one of the explanation or the hyper-explanation is absent evidence indicating at least one of a negative classification or a default classification.

18. The non-transitory computer readable medium of claim 11, wherein the at least one of the explanation or the hyper-explanation includes evidence indicating a default classification.

19. The non-transitory computer readable medium of claim 11, wherein the at least one of the explanation or the hyper-explanation includes an incorrect prior classification.

20. The non-transitory computer readable medium of claim 11, wherein at least one set of training data associated with a classifier facilitates generating the at least one of the explanation or the hyper-explanation.

21. The non-transitory computer readable medium of claim 20, wherein the at least one set of training data includes a set of nearest neighbors that facilitates generating the at least one of the explanation or the hyper-explanation.

22. The computer readable medium of claim 10, wherein the obtaining of the at least one second classification includes determining the at least one second classification of the at least one collection based on the at least one characteristic of the at least one document.

23. The computer readable medium of claim 10, wherein the items include at least one of a (i) a plurality of words, (ii) a combination of words, (iii) at least one Uniform Resource Locator, or (iv) at least one locations visited by at least one device.

24. A method for generating information associated with at least one first classification of a collection, comprising:

(a) identifying at least one characteristic of the collection, wherein the at least one characteristic includes a plurality of items;

(b) obtaining at least one second classification of the collection based on the at least one characteristic of the collection;

(c) removing at least one of the items from the at least one document;

(d) obtaining the at least one first classification based on the removal of the at least one of the items; and

(e) using a computer hardware arrangement, generating the information associated with the at least one first classification of the collection by repeating procedures (c) and (d) until the at least one first classification is different than the at least one second classification.

25. The method of claim 24, wherein the collection includes at least one document.

26. The method of claim 24, wherein the items include at least one of a (i) a plurality of words, (ii) a combination of words, (iii) at least one Uniform Resource Locator, or (iv) at least one locations visited by at least one device.

27. A system configured to generate information associated with at least one first classification of a collection, comprising:

a processing arrangement configured to;

(a) identify at least one first characteristic of the collection, wherein the at least one first characteristic includes a plurality of items;

(b) obtain at least one second classification of the collection based on the at least one first characteristic of the collection;

(c) remove at least one of the items from the at least one document;

(d) obtain the at least one first classification based on the removal of the at least one of the items; and

(e) generate the information associated with the at least one first classification of the collection by repeating procedures (c) and (d) until the at least one first classification is different than the at least one second classification.

28. The system of claim 27, wherein the collection includes at least one document.

29. The system of claim 27, wherein the items include at least one of a (i) a plurality of words, (ii) a combination of words, (iii) at least one Uniform Resource Locator, or (iv) at least one locations visited by at least one device.