Automated classification algorithm comprising at least one input-invariant part

• US 8,027,941 B2
• Filed: 09/14/2007
• Issued: 09/27/2011
• Est. Priority Date: 09/14/2007
• Status: Active Grant

• Current Assignee: Accenture Global Services Limited (Accenture PLC)
• Original Assignee: Accenture Global Services Limited (Accenture PLC)
• Inventors: Ghani, Rayid, Probst, Katharina
• Primary Examiner(s): Gaffin; Jeffrey A
• Assistant Examiner(s): KENNEDY, ADRIAN L
• Application Number:
  US11/855,493
• Publication Number:
  US 20090076989A1
• Time in Patent Office: 1,474 Days
• Field of Search: None
• US Class Current: 706/14
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A classification algorithm is separated into one or more input-invariant parts and one or more input-dependent classification parts. The input-invariant parts of the classification algorithm capture the underlying and unchanging relationships between the plurality of data elements being operated upon by the classification algorithm, whereas the one or more classification parts embody the probabilistic labeling of the data elements according to the various classifications. For any given iteration, a user'"'"'s input is used to modify at least one classification part of the algorithm. Recalculated classification parts (i.e., updated classification results) are determined based on computationally simple combinations of the one or more modified classification parts and the one or more input-invariant parts. Preferably, a graphical user interface is used to solicit user input. In this manner, wait times between user feedback iterations can be dramatically reduced, thereby making application of active learning to classification tasks a practical reality.

Claims

1. In a system, implemented by at least one processing device, based on a classification algorithm operating upon classifiable electronic data, a method for incorporating user input concerning classification of a plurality of data elements in the classifiable electronic data, the method comprising:

calculating a first input-invariant part, independent of classification probabilities for the plurality of data elements, of the classification algorithm;

receiving user input concerning classification of at least one data element of the plurality of data elements;

modifying a first classification part of the classification algorithm based on the user input to provide a modified first classification part; and

calculating a recalculated first classification part based on the modified first classification part and the first input-invariant part,

wherein the recalculated first classification part comprises first classification probabilities for at least a portion of the plurality of data elements.

2. The method of claim 1, further comprising:

calculating a second input-invariant part of the classification algorithm; and

calculating a recalculated second classification part of the classification algorithm based on the modified first classification part and the second input-invariant part,

wherein the recalculated second classification part at least indicates second classification probabilities for the portion of the plurality of data elements.

3. The method of claim 2, further comprising:

calculating final classification probabilities for the portion of the plurality of data elements based on the first classification probabilities and the second classification probabilities.

4. The method of claim 1, wherein the classification algorithm comprises a modified co-EM algorithm.

5. The method of claim 1, further comprising receiving the user input via a user interface.

6. The method of claim 5, further comprising:

determining at least one candidate data element of the plurality of data elements for prompting the user input; and

presenting an input query concerning the at least candidate data element via the user interface,

wherein the user input is received in response to the input query.

7. An apparatus, implemented by at least one processing device, for performing classification based on a classification algorithm operating upon classifiable electronic data, and incorporating user input concerning classification of a plurality of data elements in the classifiable electronic data, the apparatus comprising:

an input-invariant calculation component operative to calculate a first input-invariant part, independent of classification probabilities for the plurality of data elements, of the classification algorithm;

a user input component operative to receive user input concerning classification of at least one data element of the plurality of data elements; and

a classification calculation component, in communication with the input-invariant calculation component and the user input component, operative to modify a first classification part of the classification algorithm based on the user input to provide a modified first classification part, and to calculate a recalculated first classification part based on the modified first classification part and the first input-invariant part, wherein the first classification part comprises first classification probabilities for at least a portion of the plurality of data elements.

8. The apparatus of claim 7, the input-invariant calculation component being further operative to calculate a second input-invariant part of the classification algorithm, and the classification calculation component being further operative to calculate a recalculated second classification part of the classification algorithm based on the modified first classification part and the second input-invariant part, wherein the recalculated second classification part at least indicates second classification probabilities of the portion of the plurality of data elements.

9. The apparatus of claim 8, the classification calculation component being further operative to calculate final classification probabilities for the portion of the plurality of data elements based on the first classification probabilities and the second classification probabilities.

10. The apparatus of claim 7, further comprising:

a user interface in communication with the classification calculation component and operative to receive the user input.

11. The apparatus of claim 10, further comprising:

a candidate selection component, in communication with the classification calculation component and the user interface, operative to determine at least one candidate data element of the plurality of data elements for prompting the user input, and to provide an input query concerning the at least one candidate data element to the user interface for presentation to a user of the apparatus.

12. The apparatus of claim 11, wherein the user interface comprises a graphical user interface.

13. An apparatus for performing classification based on a classification algorithm operating upon classifiable electronic data, and incorporating user input concerning classification of a plurality of data elements in the classifiable electronic data, the apparatus comprising:

at least one processor; and

at least one storage device, coupled to the at least one processor, comprising processor-executable instructions that, when executed by the at least one processor, cause the at least one processor to;

calculate a first input-invariant part, independent of classification probabilities for the plurality of data elements, of the classification algorithm;

receive user input concerning classification of at least one data element of the plurality of data elements;

modify a first classification part of the classification algorithm based on the user input to provide a modified first classification part; and

calculate a recalculated first classification part based on the modified first classification part and the first input-invariant part,

wherein the recalculated first classification part comprises first classification probabilities for at least a portion of the plurality of data elements.

14. The apparatus of claim 13, the at least one storage device further comprising processor-executable instructions that, when executed by the at least one processor, cause the at least one processor to:

calculate a second input-invariant part of the classification algorithm; and

calculate a recalculated second classification part of the classification algorithm based on the modified first classification part and the second input-invariant part,

wherein the recalculated second classification part at least indicates second classification probabilities for the portion of the plurality of data elements.

15. The apparatus of claim 14, the at least one storage device further comprising processor-executable instructions that, when executed by the at least one processor, cause the at least one processor to:

calculate final classification probabilities for the portion of the plurality of data elements based on the first classification probabilities and the second classification probabilities.

16. The apparatus of claim 13 further comprising a display and at least one user input device in communication with the at least one processor, the at least one storage device further comprising processor-executable instructions that, when executed by the at least one processor, cause the at least one processor to:

determine at least one candidate data element of the plurality of data elements for prompting the user input;

present an input query concerning the at least candidate data element via the display; and

receiving the user input in response to the input query via the at least one user input device.