Data processing: artificial intelligence – Machine learning
Reexamination Certificate
2002-04-05
2004-07-13
Davis, George B. (Department: 2122)
Data processing: artificial intelligence
Machine learning
C706S015000, C706S013000
Reexamination Certificate
active
06763338
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to decision making and, alternatively, to learning, using a computing machine.
2. Discussion of the Related Art
Modern research and technology have made computing devices commonplace in the lives of many individuals. Many modern devices, appliances and conveniences include various amounts of computing or processing power. Devices that include computing capabilities often make decisions about objects based on whatever input data about the object is available to the device.
Such decisions may include, among others:
Selections of alternatives, help messages or hints about how to use the device, are presented to the user of the device;
Selections of entertainment, advertising, or other options or information to be shown to, or recorded for, the user;
Assessments or evaluations of whoever is using the device or of the environment or context in which the device is being used; or
Predictions about a system that the device attempts to model.
Many computing devices include a module or function that classifies objects, models preferences or evaluates alternatives. Such evaluators can decide which one or ones of a set of alternatives best apply to a particular object, as described by the input data available about that object, which may be quite limited.
Some evaluators are based on machine learning, that is, the evaluator has been trained as to what is the correct decision, or is trained over time as the device is actually used. In other cases, evaluators are hand crafted by the programmers who designed the device. In still other cases, experts formulate “rules of thumb” or “operating parameters,” which are then entered into a computer program, model or expert system.
There are many known ways of representing or implementing a machine evaluator, including, among others; decision trees, belief networks, neural networks, static mathematical models, expert systems or computer programs. Many of these types of evaluators have known ways of using training data to train new instances of evaluators for new classification, selection or prediction problems. Typically, such training data includes many instances of input data from various example objects, with each instance labeled as to the alternative or alternatives that correctly apply to that object.
An evaluator is usually trained to be applied to objects not seen before. Thus, it is rare that one can speak confidently of having found the best or optimal evaluator. In fact, when the same machine learning model or type of evaluator is run using different batches of training data, different evaluators may be produced.
Further, some machine learning methods are non-deterministic, that is, they are likely to yield a different result each time the model is trained. Such methods include, among others; evolutionary training methods, population based training methods, genetic algorithms or genetic programming. For such methods, the result of the training process is typically not be a single evaluator. Rather, the result may be a number of evaluators, often ranked by some accuracy or fitness measure.
Thus, any particular machine decision problem can be approached using different types of evaluators, or using different instances of evaluators of the same type. One option is to select a single evaluator and use it exclusively. The type of evaluator selected may simply be chosen based on the preferences and familiarity of the person implementing the system.
A second option is to obtain a set of reasonably good evaluators for a particular machine decision problem and combine the result from each evaluator. Given the inaccuracy, uncertainty and other limitations of machine learning and machine decision making, this second approach may be advantageous for many problems.
However, this second option requires combining results from a number of evaluators into making an overall or aggregate decision. One way to combine decisions is to give each evaluator one vote, or a vote weighted by a factor such as the expected accuracy of that evaluator. If one alternative receives a majority of the weighted votes, then the majority should rule. However, there may not be a majority winner.
Another way to combine decisions is pluralistic voting, in which the alternative that receives the most votes is the aggregate decision, regardless of how few votes that alternative receives and regardless of how strong the other alternatives are. However, some observers of the 2000 U.S. presidential election feel there are significant problems with single vote pluralistic voting, especially when the voters are largely split as to their first preference.
Other observers cite the 1970 race for U.S. Senator from New York, in which a liberal Republican and a liberal Democrat split approximately 5 out of 9 votes. This split left conservative James Buckley winning with a plurality of approximately 4 out of 9 votes. To some observers, this result was unfair or inaccurate because a majority of the voters would have preferred either of the liberal candidates to Buckley. That claim could have been proven if the votes had recorded first, second and third preferences from each voter, or if Buckley and the candidate who came in second had faced a run off election.
A related effect occurs when a voter is pragmatically dishonest. A person may cast their vote for the candidate they prefer out of those who they feel have a realistic chance to win, rather than supporting a truly preferred long shot.
Training or designing a computer model to recognize consumer preferences, for example, is complex. It may be undesirable, difficult or infeasible to have such a model somehow adjust the vote it casts by taking into account other likely votes. A way to compute an aggregate decision, based on intermediate decisions as to which alternative or alternatives best apply to an object, has not been known to be available.
SUMMARY OF THE INVENTION
The present invention provides a solution to the problems identified above by providing an automated method and apparatus to employ intermediate decisions as to the application of alternatives to an object to compute an overall or aggregate decision.
According to the invention, at least two intermediate rankings are obtained, each of which ranks each of at least three alternatives with respect to an object. For each intermediate ranking, a corresponding series of preferences is initialized. Each series is ordered from a first preference to a last preference. Each series initially groups each alternative into a preference selected based on the corresponding intermediate ranking. In the case of a tie, each preference may include more than one alternative. Based on all the series of preferences, a weak alternative is selected and removed from each series. Each series is accordingly re-grouped into updated preferences, based on the intermediate ranking corresponding to the series.
When each series contains fewer than a first threshold number of alternatives, then the invention stops and the aggregate decision includes the alternatives remaining in the series. Otherwise, the method repeats the selecting, the removing, the re-grouping and the deciding until an aggregate decision is made.
Various embodiments of the invention include deciding the intermediate rankings based on a technique selected from: a machine learning technique; a decision tree; a belief network; a neural network; a static model; a program; an evolutionary training method; or some other technique. In some embodiments of the invention it may be advantageous to base different evaluators on different techniques.
Some embodiments of the invention can be applied to classification problems.
The alternatives include classifications of the object and the aggregate decision classifies the object.
Other embodiments of the invention can be applied to prediction problems.
The alternatives include a set of future behaviors of the object and the aggregate decision predicts a likely one or more of the future behaviors.
Yet other embodiments of
Davis George B.
Hewlett--Packard Development Company, L.P.
LandOfFree
Machine decisions based on preferential voting techniques does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Machine decisions based on preferential voting techniques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Machine decisions based on preferential voting techniques will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3218289