Controller for controlling a system

• US 20030004777A1
• Filed: 03/22/2001
• Published: 01/02/2003
• Est. Priority Date: 03/07/2001
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Omniture Incorporated (Adobe Inc.)
• Inventors: Phillips, Alan Paul Rolleston
• Granted Patent: US 7,260,551 B2
• Time in Patent Office: Days
• US Class Current: 705/10
• 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
• CPC Class Codes: G06Q 10/0635 Risk analysis of enterprise or organisation activities
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 10/0639 Performance analysis of employees; Performance analysis of enterprise or organisation operations
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities

Abstract

The present disclosure relates to a controller for controlling a system, capable of presentation of a plurality of candidate propositions resulting in a response performance, in order to optimise an objective function of the system. The controller has a means for storing, according to candidate proposition, a representation of the response performance in actual use of respective propositions; means for assessing which candidate proposition is likely to result in the lowest expected regret after the next presentation on the basis of an understanding of the probability distribution of the response performance of all of the plurality of candidate propositions; where regret is a term used for the shortfall in response performance between always presenting a true best candidate proposition and using the candidate proposition actually presented.

Claims

1. A controller for controlling a system, capable of presentation of a plurality of candidate propositions resulting in a response performance, in order to optimise an objective function of the system, the controller comprising:

means for storing, according to candidate proposition, a representation of the response performance in actual use of respective propositions;

means for assessing which candidate proposition is likely to result in the lowest expected regret after the next presentation on the basis of an understanding of the probability distribution of the response performance of all of the plurality of candidate propositions;

where regret is a term used for the shortfall in response performance between always presenting a true best candidate proposition and using the candidate proposition actually presented.

2. A controller according to claim 1 wherein the assessment means includes means for controlling the growth of the expected regret.

3. A controller according to claim 1 wherein the assessment means assesses which proposition is likely to result in the lowest expected regret on the basis of an optimal candidate proposition which has the mean of said probability distribution.

4. A controller according to claim 3 wherein the assessment means evaluates the cost or losses associated with presenting a sub-optimal candidate proposition and the gain or benefit associated with knowing the true position of the optimal candidate proposition on said probability distribution.

5. A controller according to claim 3 wherein the assessment means assesses which proposition is likely to result in the lowest expected regret according to an assumption that the current best observed proposition is assumed to have zero uncertainty around its mean or expected response performance.

6. A controller according to claim 1 wherein the assessment means assesses which proposition is likely to result in the lowest expected regret according to an assumption of a Student'"'"'s distribution and evaluation of Student'"'"'s t parameters as the basis for estimating probabilities of unequal or equal response states between the proposition with the current expected best response and any other candidate proposition.

7. A controller according to claim 1 wherein the assessment means uses a Monte Carlo algorithm to provide understanding of the probability distribution of the response performance of all of the plurality of candidate propositions and either selects the proposition that contributes most to the expected regret estimate, or selects a proposition with probability proportional to its contribution to the expected regret estimate.

8. A controller according to claim 1 further comprising temporal depreciation means for applying a temporal depreciation factor to the stored representations of the response performance in order to depreciate the significance of the representations over time.

9. A controller according to claim 1 further comprising means for forcing the presentation of each candidate proposition a minimum number of times or at a minimum rate.

10. A controller according to claim 9 wherein the temporal depreciation means, for each candidate proposition, applies a different temporal depreciation factor to the stored representations of the response performance thereof.

11. A controller according to claim 1 wherein the candidate proposition is a candidate action option and the presentation thereof comprises a selection.

12. A control device at a particular ranked level comprising:

a correspondingly ranked system having a plurality of sub-rank systems respectively representing a candidate function, at least one of the sub-rank systems having a sub-rank controller comprising a controller according to any preceding claim; and

a ranked controller for controlling the ranked system, capable of use of the plurality of candidate functions to result in a response performance, in order to optimise an objective function of the ranked system;

wherein the ranked controller comprises;

means for storing, according to candidate function, a representation of the response performance in actual use of respective candidate functions;

means for assessing which candidate function is likely to result in the lowest expected regret after the next use of a sub-rank system on the basis of an understanding of the probability distribution of the response performance of all of the plurality of sub-rank systems;

where regret is a term used for the shortfall in response performance between always using the true best sub-rank system and using the sub-rank system actually used.

13. A control device according to claim 12 wherein one sub-rank system includes means for randomly selecting from a plurality of respective candidate propositions.

14. A control device according to claim 12 having a sub-rank controller with an assessment means assessing irrespective of the interaction scenario occurring during the response to a candidate proposition.

16. A control device according to claim 13 in which statistical significances of the difference between the response performance of the sub-rank system and another sub-rank system or any combination of other sub-rank systems is used as a control input.

17. A system controller comprising a plurality of control devices according to any one of claims 12 to 16 arranged in a hierarchical structure of rank levels.

15. A control device according to claim having a sub-rank controller with an assessment means assessing according to the interaction scenario occurring during the response to a candidate proposition.