Methods and systems for interactive computing

• US 20080183648A1
• Filed: 01/31/2007
• Published: 07/31/2008
• Est. Priority Date: 01/31/2006
• Status: Active Grant

• Current Assignee: Board of Trustees of The University of Illinois
• Original Assignee: Board of Trustees of The University of Illinois
• Inventors: Llora, Xavier F., Goldberg, David E., Sastry, Kumara
• Granted Patent: US 7,979,365 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

Methods and systems for creating a synthetic surrogate fitness function. User decisions are received representing fitness for a plurality of solutions. A partial ordering of the plurality of solutions is provided based on the received user decisions, wherein at least some of the plurality of solutions are represented to have a greater relative fitness than other of the plurality of solutions. A complete order of at least the plurality of solutions is induced based on the normalized partial ordering. A synthetic surrogate fitness function is generated using the induced complete order.

Claims

1. A method for optimizing a solution comprising:

a) creating at least one solution;

b) presenting said at least one solution to a user;

c) receiving input from the user representing subjective fitness of the at least one solution;

d) providing a partial ordering of a plurality of solutions based on said received input;

e) inducing a complete order of at least the plurality of solutions presented to the user based on said provided partial ordering;

f) generating a synthetic surrogate subjective fitness function using said induced complete order;

g) creating at least one new solution using said generated synthetic surrogate subjective fitness.

2. The method of claim 1, further comprising:

h) presenting said at least one new solution to the user;

repeating c)-h) until stopping criteria are met.

3. The method of claim 1, wherein said creating at least one new solution comprises generating a first group of solutions using said generated synthetic subjective surrogate fitness, generating a second group of solutions using said created plurality of solutions, and combining the generated first group and the generated second group.

4. The method of claim 1, wherein said generating a synthetic subjective surrogate fitness comprises:

training a surrogate function using said induced complete order.

5. The method of claim 4, wherein said training is further based on determined fitness values for the larger plurality of solutions.

6. The method of claim 1, further comprising:

optimizing said synthetic surrogate fitness function.

7. The method of claim 6, wherein said optimized synthetic surrogate subjective fitness function comprises an estimation of distribution algorithm (EDA).

8. The method of claim 7, wherein said creating at least one new solution comprises sampling from the EDA.

9. The method of claim 1, wherein said creating comprises creating a plurality of solutions, wherein said presenting comprises presenting said created plurality of solutions to the user in groups of two, and wherein said receiving input from the user comprises receiving an input representing:

a) the first of the group of two has greater fitness than the second of the group of two;

b) the second of the group of two has greater fitness than the first of the group of two;

OR

c) neither a) nor b).

10. The method of claim 1, wherein said providing a partial ordering comprises providing a partial ordering graph G <

V, E>

, where vertex V represents solutions presented to the user so far, and edge E represents received input from the user representing a pair-wise comparison between solutions.

11. The method of claim 10, further comprising:

providing a normalized directed partial ordering based on said provided partial ordering graph, wherein all edges E in the directed partial ordering graph comprise one of a greater-than relation and a lesser-than relation.

12. The method of claim 10, wherein said inducing a complete order comprises:

for each vertex V in G, determining a number of other vertices δ

(v) that are dominated by V, and determining a number of other vertices φ

(v) that dominate vertex V;

determining a synthetic subjective fitness for each vertex V using δ

(v) and φ

(v);

ranking each vertex V using said determined synthetic subjective fitness.

13. The method of claim 11, further comprising:

based on said normalized directed partial ordering, determining that an inconsistency in user decisions is present if at least one vertex is both dominated by a second vertex and dominates the second vertex.

14. The method of claim 13, further comprising:

correcting said determined inconsistency.

15. The method of claim 14, wherein said correcting comprises:

removing at least one edge E from the directed partial ordering.

16. The method of claim 15, wherein said removing is based on at least one of recency, statistical methods, input from the user, and input from an outside source.

33. A computer program product useful to optimize a solution set, the computer program product comprising computer readable instructions stored on a computer readable memory or medium that when executed by one or more computers cause one or more computers to perform the steps in the method of claim 1.

17. A method for determining decision consistency in an interactive session, the method comprising:

receiving user decisions representing fitness for a plurality of solutions;

providing a partial ordering of the plurality of solutions based on said received user decisions, wherein at least some of the plurality of solutions are represented to have a greater relative fitness than other of the plurality of solutions;

normalizing said partial ordering;

based on said normalized partial ordering, determining that an inconsistency exists if at least a first solution in said normalized partial ordering is represented to have a greater relative fitness than a second solution and if the second solution is represented to have a greater relative fitness than the first solution.

18. The method of claim 17, wherein said providing a partial ordering comprises:

providing a partial ordering graph G <

V, E>

, where vertex V represents solutions presented to the user so far, and edge E represents received input from the user representing a pair-wise comparison between solutions.

19. The method of claim 18, wherein said normalizing comprises setting every edge E in graph G to one of a greater-than relation and a lesser than relation based on said partial ordering.

20. The method of claim 18, further comprising:

based on said partial ordering, for each vertex V in G, determining vertices that are dominated by V, and determining vertices that dominate vertex V;

wherein an inconsistency exists if at least one vertex V is both dominated by a second vertex and dominates the second vertex.

21. The method of claim 17, further comprising:

removing the inconsistency by removing one or more edges E.

22. The method of claim 21, wherein said removing is based on at least one of recency, statistical methods, input from the user, and input from an outside source.

34. A computer program product useful to optimize a solution set, the computer program product comprising computer readable instructions stored on a computer readable memory or medium that when executed by one or more computers cause one or more computers to perform the steps in the method of claim 17.

23. A method for creating a synthetic surrogate fitness function comprising:

receiving user decisions representing fitness for a plurality of solutions;

providing a partial ordering of the plurality of solutions based on said received user decisions, wherein at least some of the plurality of solutions are represented to have a greater relative fitness than other of the plurality of solutions;

normalizing said partial ordering;

inducing a complete order of at least the plurality of solutions based on said normalized partial ordering;

generating the synthetic surrogate fitness function using said induced complete order.

24. The method of claim 23, wherein said generating is further based on fitness values determined from said received user decisions.

25. The method of claim 23, wherein said partial ordering is represented by a graph G <

V, E>

, where vertex V represents solutions presented to the user so far, and edge E represents received input from the user representing a pair-wise comparison between solutions.

26. The method of claim 25, wherein said normalizing comprises adjusting said partial ordering such that all edges E in said normalized partial ordering graph comprise one of a greater-than relation and a lesser-than relation.

27. The method of claim 26, said inducing a complete order comprises:

for each vertex V in G, determining a number of other vertices δ

(v) that are dominated by V, and determining a number of other vertices φ

(v) that dominate vertex V;

determining a synthetic subjective fitness for each vertex V using δ

(v) and φ

(v);

ranking each vertex V using said determined synthetic subjective fitness.

28. The method of claim 23, further comprising:

based on said normalizing, determining that an inconsistency in user decisions is present if at least one vertex is both dominated by a second vertex and dominates the second vertex.

29. The method of claim 28, further comprising:

correcting said determined inconsistency.

30. The method of claim 23, further comprising:

generating at least one new solution using said generated synthetic surrogate fitness function;

presenting said generated at least one new solution to the user.

35. A computer program product useful to optimize a solution set, the computer program product comprising computer readable instructions stored on a computer readable memory or medium that when executed by one or more computers cause one or more computers to perform the steps in the method of claim 23.

31. The method of claim 31, wherein said presented at least one new solution is combined with at least one previously presented solution before said presenting.

32. A method for optimizing a solution comprising:

a) presenting to a user a plurality of choices representing a plurality of solutions;

b) receiving decision data representing preferences among said plurality of choices;

c) generating a model representing fitness using said received decision data;

d) generating new solutions using said generated model;

e) presenting at least one or more of said generated new solutions to the user as a new plurality of choices;

f) repeating steps b)-e) over at least one additional iteration.

36. A computer program product useful to optimize a solution set, the computer program product comprising computer readable instructions stored on a computer readable memory or medium that when executed by one or more computers cause one or more computers to perform the steps in the method of claim 32.