Machine decisions based on preferential voting techniques

• US 6,763,338 B2
• Filed: 04/05/2002
• Issued: 07/13/2004
• Est. Priority Date: 04/05/2002
• Status: Expired due to Term

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kirshenbaum, Evan R.
• Primary Examiner(s): Davis, George B.
• Application Number:
  US10/116,835
• Publication Number:
  US 20030191726A1
• Time in Patent Office: 830 Days
• Field of Search: 706/12, 706/15, 706/13
• US Class Current: 706/12
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06N 3/086 using evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method and apparatus for computing an overall or aggregate decision based on intermediate decisions as to which of a set of alternatives best characterize an object. The alternatives are partitioned into at least two series of preferences corresponding to at least two intermediate rankings. Various embodiments may base the intermediate rankings on: a machine learning technique; a decision tree; a belief network; a neural network; a static model; a program; or an evolutionary training method. Based on the preferences, a weak alternative is selected and removed from the series. The selection of the weak alternative may include identifying which alternatives lose pairwise to the other alternatives, are excluded from the first preferences, are included in the last preferences, or have a lowest average preference ranking. The selecting and removing continue until the remaining alternatives are the aggregate decision. Various embodiments may be applied to classification problems, prediction problems or selection problems.

Claims

1. A method of computing an aggregate decision about an object, the method comprising:

obtaining at least two intermediate rankings, each of which ranks at least three alternatives with respect to the object;

initializing at least two series of preferences, wherein each series corresponds to one of the intermediate rankings, each series is ordered from a first preference to a last preference, each series initially groups each alternative into one of the preferences selected based on the corresponding intermediate ranking, and each preference includes at least one of the alternatives;

selecting, based on the preferences, at least one of the alternatives as a weak alternative;

removing at least one weak alternative from each series;

then

re-grouping each series into preferences based on the intermediate ranking corresponding to the series;

deciding, when each series contains less than a first threshold number of the alternatives, that the aggregate decision includes the alternatives remaining in the series; and

repeating selecting, removing, re-grouping, and deciding until an aggregate decision is made.

2. The method of claim 1, and further comprising deciding at least one of the intermediate rankings based on a technique selected from at least one of a machine learning technique, a decision tree, a belief network, a neural network, a static model, a program, and an evolutionary training method.

3. The method of claim 2, and further comprising deciding at least two of the intermediate rankings based on at least two different techniques each selected from at least one of a machine learning technique, a decision tree, a belief network, a neural network, a static model, a program, and an evolutionary training method.

4. The method of claim 1, wherein the alternatives include classifications of the object and the aggregate decision classifies the object.

5. The method of claim 1, wherein the alternatives include a set of future behaviors of the object and the aggregate decision predicts a likely one of the future behaviors.

6. The method of claim 1, wherein the alternatives include options and the aggregate decision selects at least one of the options based on the object.

7. The method of claim 1, wherein each intermediate ranking is represented in the selecting by at least two preferences.

8. The method of claim 1, wherein the selection of the weak alternative includes identifying which alternatives are preferred over other alternatives, and in every series every other alternative is preferred over the weak alternative.

9. The method of claim 1, wherein the selection of the weak alternative includes identifying which alternatives are preferred over other alternatives, and at least a first percentage of the alternatives are preferred over the weak alternative in at least a second percentage of the series.

10. The method of claim 1, wherein the selection of the weak alternative includes identifying which alternatives are in the first preference of each series, and no other alternative is in the first preference in fewer series than the weak alternative.

11. The method of claim 1, wherein the selection of the weak alternative includes identifying which alternatives are in a set of first preferences within each series, and there is less than a selected percentage of the alternatives that are omitted from the set of first preferences more than the weak alternative is omitted from the set of first preferences.

12. The method of claim 1, wherein the selection of the weak alternative includes identifying which alternatives are in the last preference of each series, and no other alternative is in the last preference in more series than the weak alternative.

13. The method of claim 1, wherein the selection of the weak alternative includes identifying which alternatives are in a set of last preferences within each series, and less than a selected percentage of the alternatives are in the set of last preferences more than the weak alternative is in the set of last preferences.

14. The method of claim 1, wherein the selection of the weak alternative includes giving to each alternative a number of points based on each preference in each series, the number of points decreasing for lower preferences, and a total of the points received by the weak alternative is no more than a total of the points received by any other alternative.

15. The method of claim 1, wherein the selection of the weak alternative includes calculating an average preference for each alternative, and the average preference of less than a selected percentage of the alternatives is higher than the average preference of the weak alternative.

16. The method of claim 1, wherein the selection of the weak alternative includes identifying which alternatives are in a set of first preferences within each series, and less than a selected percentage of the series have the weak alternative in the set of first preferences.

17. The method of claim 1, wherein each intermediate ranking has a weighting factor and the selection of the weak alternative applies to each preference the weighting factor of the intermediate ranking corresponding to the preference.

18. The method of claim 1, and further comprising selecting a particular alternative to be included in the aggregate decision and removing the particular alternative from each series.

19. The method of claim 18, wherein the particular alternative is selected from at least one of:

one of the alternatives that is in the first preference of at least a second threshold number of the series;

one of the alternatives that is preferred over every other alternative in every series; and

one of the alternatives that is preferred over at least a first percentage of the alternatives in at least a second percentage of the series.

20. The method of claim 1, wherein the first threshold number is selected from a predetermined number, a predetermined percentage of the alternatives, and a number that is adjusted during the operation of the method.

21. A computer readable media containing instructions that, when the instructions are read and executed by a system, control a process comprising:

obtaining at least two intermediate rankings, each of which ranks at least three alternatives with respect to the object;

initializing least two series of preferences, wherein each series corresponds to one of the intermediate rankings, each series is ordered from a first preference to a last preference, each series initially groups each alternative into one of the preferences selected based on the corresponding intermediate ranking, and each preference includes at least one of the alternatives;

selecting, based on the preferences, at least one of the alternatives as a weak alternative;

removing at least one weak alternative from each series;

then

re-grouping each series into preferences based on the intermediate ranking corresponding to the series;

deciding, when each series contains less than a first threshold number of the alternatives, that the aggregate decision includes the alternatives remaining in the series; and

repeating selecting, removing, re-grouping, and deciding until an aggregate decision is made.

22. The computer readable media of claim 21, wherein the process further comprises deciding at least two of the intermediate rankings based on at least two different techniques each selected from at least one of a machine learning technique, a decision tree, a belief network, a neural network, a static model, a program, and an evolutionary training method.

23. The computer readable media of claim 21, wherein the aggregate decision is selected from at least one of a decision that classifies the object, a decision that predicts a likely future behavior of the object and a decision that selects among a set of options based on the object.

24. The computer readable media of claim 21, wherein the selection of the weak alternative includes identifying which alternatives are preferred over other alternatives, and at least a first percentage of the alternatives are preferred over the weak alternative in at least a second percentage of the series.

25. The computer readable media of claim 21, wherein the selection of the weak alternative includes identifying which alternatives are in a set of first preferences within each series, and there is less than a selected percentage of the alternatives that are omitted from the set of first preferences more than the weak alternative is omitted from the set of first preferences.

26. The computer readable media of claim 21, wherein the selection of the weak alternative includes identifying which alternatives are in a set of last preferences within each series, and less than a selected percentage of the alternatives are in the set of last preferences more than the weak alternative is in the set of last preferences.

27. The computer readable media of claim 21, wherein the selection of the weak alternative includes calculating an average preference for each alternative, and the average preference of no more than a selected percentage of the alternatives is higher than the average preference of the weak alternative.

28. The computer readable media of claim 21, wherein the selection of the weak alternative identifying which alternatives are in a set of first preferences within every series, and less than a selected percentage of the series have the weak alternative in the set of first preferences.

29. An apparatus configured to compute an aggregate decision about an object, the apparatus comprising:

an interface configured to obtain at least two intermediate rankings, each of which ranks at least three alternatives with respect to the object;

a processor configured to initialize at least two series of preferences, each series corresponding to one of the intermediate rankings, each series being ordered from a first preference to a last preference, each series initially grouping each alternative into one of the preferences selected based on the corresponding intermediate ranking, and each preference including at least one of the alternatives;

wherein the processor is further configured to select, based on the preferences, at least one of the alternatives as a weak alternative, to remove the weak alternative from each series, to accordingly re-group each series into preferences based on the intermediate ranking corresponding to the series, to decide, when each series contains less than a threshold number of the alternatives, that the aggregate decision includes the alternatives remaining in the series, and to repeat the selecting, the removing, the re-grouping, and the deciding until an aggregate decision is made.

30. A means for computing an aggregate decision about an object, the means comprising:

a means for obtaining at least two intermediate rankings, each of which ranks at least three alternatives with respect to the object;

a means for initializing at least two series of preferences, each series corresponding to one of the intermediate rankings, each series being ordered from a first preference to a last preference, each series initially grouping each alternative into one of the preferences selected based on the corresponding intermediate ranking, and each preference including at least one of the alternatives;

a means for selecting, based on the preferences, an alternative as a weak alternative;

a means for removing the weak alternative from each of the series, and accordingly re-grouping each series into preferences based on the intermediate ranking corresponding to the series;

a means for deciding, when each series contains less than a threshold number of the alternatives, that the aggregate decision includes the alternatives remaining in the series; and

a means for repeating the selecting, the removing, the re-grouping, and the deciding until an aggregate decision is made.