Determining utility functions from ordenal rankings

• US 7,392,231 B2
• Filed: 12/03/2002
• Issued: 06/24/2008
• Est. Priority Date: 12/03/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Gupta, Manish, Basak, Jayanta
• Primary Examiner(s): Knight; Anthony
• Assistant Examiner(s): KENNEDY, ADRIAN L
• Application Number:
  US10/308,401
• Publication Number:
  US 20040107171A1
• Time in Patent Office: 2,030 Days
• Field of Search: 706 15- 44, 706/45
• US Class Current: 706/31
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A user'"'"'s preference structure in respect of alternative “objects” with which the user is presented is captured in a multi-attribute utility function. The user ranks these competing objects in order of the user'"'"'s relative preference for such objects. A utility function that defines the user'"'"'s preference structure is provided as output on the basis of this relative ranking. This technique can be used to assist a buyer in selecting between multi-attribute quotes or bids submitted by prospective suppliers to the buyer.

Claims

1. A method for determining a utility function based upon paired preferences amongst objects, the method comprising:

inputting ordered pairs of said objects, wherein;

each of said objects is represented by an attribute vector and associated with goods and services,

a number of said objects inputted is less than a total number of objects being ordered; and

ordering of each pair of said objects is determined by a user;

initializing a neural network for training;

computing a change in parameter weights of said neural network for each ordered pair of said objects inputted, wherein said change in parameter weights comprises an average change in said parameter weights for all possible pairs of said total number of objects;

calculating an error measure associated with a utility function;

revising said utility function in response to said error measure;

performing the calculating of said error measure and the revising until said error measure results in a user-defined difference between an ordered output of the ordered pairs of said objects inputted; and

automatically generating a ranked list of said total number of objects associated with numerical values of said ordered output and said goods and services, and based on the utility function as an output.

2. The method as claimed in claim 1, all the limitations of which are incorporated herein by reference, wherein the utility function is implied by said neural network that is trained using at least one pair of objects (x_i, x_j) from a set of objects.

3. The method as claimed in claim 2, all the limitations of which are incorporated herein by reference, wherein said total number of objects is fully ordered in said output.

4. The method as claimed in claim 3, all the limitations of which are incorporated herein by reference, wherein a partially ordered subset of objects (x_i, x_j) are selected from said total number of objects.

5. The method as claimed in claim 2, all the limitations of which are incorporated herein by reference, wherein the output of said neural network corresponds to said utility function.

6. The method as claimed in claim 5, all the limitations of which are incorporated herein by reference, wherein the a measure of change in the weights of said neural network comprises an average value of change in said weights of said neural network.

7. The method as claimed in claim 1, all the limitations of which are incorporated herein by reference, wherein ranked list of said total number of objects is explicitly obtained from said output of said neural network.

8. The method as claimed in claim 1, all the limitations of which are incorporated herein by reference, wherein said attribute vector is inputted into said neural network, wherein said neural network comprises:

a first layer adapted to receive said attribute vector;

a second layer connected to said first layer; and

a summation node connected to said second layer, wherein said summation node is adapted to output the utility function.

9. The method as claimed in claim 1, all the limitations of which are incorporated herein by reference, wherein said neural network comprises a feed-forward neural network.

10. The method as claimed in claim 2, all the limitations of which are incorporated herein by reference, wherein an architecture of said neural network is selected to suit a complexity of the utility function implied by the ranked list of said total number of objects.

11. A program storage device readable by computer, tangibly embodying a program of instructions executable by said computer to perform a method of determining a utility function based upon paired preferences amongst objects, the method comprising:

inputting ordered pairs of said objects, wherein;

each of said objects is represented by an attribute vector and associated with goods and services,

a number of said objects inputted is less than a total number of objects being ordered; and

ordering of each pair of said objects is determined by a user;

initializing a neural network for training;

computing a change in parameter weights of said neural network for each ordered pair of said objects inputted, wherein said change in parameter weights comprises an average change in said parameter weights for all possible pairs of said total number of objects;

calculating an error measure associated with a utility function;

revising said utility function in response to said error measure;

performing the calculating of said error measure and the revising until said error measure results in a user-defined difference between an ordered output of the ordered pairs of said objects inputted; and

automatically generating a ranked list of said total number of objects associated with numerical values of said ordered output and said goods and services, and based on the utility function as an output.

12. The program storage device as claimed in claim 11, all the limitations of which are incorporated herein by reference, wherein the utility function is implied by said neural network that is trained using at least one pair of objects (xi, xj) from a set of objects.

13. The program storage device as claimed in claim 12, all the limitations of which are incorporated herein by reference, wherein said total number of objects is fully ordered in said output.

14. The program storage device as claimed in claim 13, all the limitations of which are incorporated herein by reference, wherein a partially ordered subset of objects (x_i, x_j) are selected from said total number of objects.

15. The program storage device as claimed in claim 12, all the limitations of which are incorporated herein by reference, wherein the output of said neural network corresponds to said utility function.

16. The program storage device as claimed in claim 15, all the limitations of which are incorporated herein by reference, wherein measure of change in the weights of said neural network comprises an average value of change in said weights of said neural network.

17. The program storage device as claimed in claim 11, all the limitations of which are incorporated herein by reference, wherein the total number of objects is explicitly obtained from said output of said neural network.

18. The program storage device as claimed in claim 11, all the limitations of which are incorporated herein by reference, wherein said attribute vector is inputted into said neural network, wherein said neural network comprises:

a first layer adapted to receive said attribute vector;

a second layer connected to said first layer; and

a summation node connected to said second layer, wherein said summation node is adapted to output the utility function.

19. The program storage device as claimed in claim 11, all the limitations of which are incorporated herein by reference, wherein said neural network is a feed-forward neural network.

20. The program storage device as claimed in claim 12, all the limitations of which are incorporated herein by reference, wherein an architecture of said neural network is selected to suit a complexity of the utility function implied by the total number of objects.