Model-based and data-driven analytic support for strategy development

• US 20040181441A1
• Filed: 04/27/2004
• Published: 09/16/2004
• Est. Priority Date: 04/11/2001
• Status: Active Grant

• Current Assignee: Fair Isaac Corporation
• Original Assignee: Fair Isaac Corporation
• Inventors: Crawford, Stuart, Fung, Robert M.
• Granted Patent: US 7,930,196 B2
• Time in Patent Office: Days
• US Class Current: 705/7
• 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/0637 Strategic management or analysis, e.g. setting a goal or target of an organisation; Planning actions based on goals; Analysis or evaluation of effectiveness of goals
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

The invention provides an overall architecture for optimal strategy design using both historical data and human expertise. The presently preferred architecture supports the tasks of strategy design and strategy analysis, and provides extensions to influence diagrams, translation of an influence diagram as a nonlinear optimization problem, and use of induction after optimization to derive decision rules.

Claims

1. An apparatus for strategy design and strategy analysis, comprising:

one or more extensions to influence diagram methodology;

a mechanism for translation of an influence diagram as a nonlinear optimization problem; and

a mechanism for induction after optimization to derive decision rules.

2. The apparatus of claim 1, wherein said influence diagram methodology comprises any of a Bayesian network, Bayes'"'"' Net, and Bayesian model.

3. The apparatus of claim 1, wherein said extensions to influence diagram methodology comprise any of:

a mechanism for effecting constrained optimization, which places constraints on an optimization in an influence diagram;

a mechanism for effecting dataset-based optimization over an explicitly specified set of cases which comprise a representative population, as well as over a set of cases implicitly specified by joint prior distributions of decision keys; and

a mechanism for mapping a decision model to a dataset file to map variables in an influence diagram to columns of a dataset.

4. The apparatus of claim 1, wherein said mechanism for translation of an influence diagram as a nonlinear optimization problem allows an influence diagram to contain continuous variables with complex functional forms, a specification of high-dimensional representative populations, and constraints.

5. The apparatus of claim 1, wherein said mechanism for induction derives simpler decision rules from many cases to allow for strategies that are more understandable, easier to edit, and easier to implement than at least one action provided in the raw optimization results.

6. A method for using strategy optimization, comprising the steps of:

creating a strategy optimization influence diagram and a representative population to model a decision situation mathematically;

formatting said strategy optimization influence diagram as a nonlinear optimization problem over a representative population;

using nonlinear optimization techniques to assign at least one action to each case in a representative population;

creating a strategy table containing all cases in said representative population, along with at least one assigned action for each case;

applying induction techniques to said strategy table to derive a set of rules from data; and

operationalizing a set of rules derived by induction through a decision engine.

7. The method of claim 6, wherein said influence diagram comprises any of a Bayesian network, Bayes'"'"' Net, and Bayesian model.

8. The method of claim 6, wherein said step of modeling a decision situation formulates and specifies a decision situation as a decision model, using a modeling language based on influence diagrams.

9. The method of claim 7, wherein said modeling language comprises any of the steps of:

constraining optimization by associating a set of constraints with said decision model;

performing dataset-based optimization over an explicitly specified set of cases; and

mapping said decision model to a dataset file, wherein each decision key in said decision model is mapped with a column in a dataset.

10. The method of claim 6, wherein said step of formatting said strategy optimization influence diagram as a nonlinear optimization problem over a representative population formulates a nonlinear optimization problem that corresponds substantially exactly to a decision model specified in said modeling language;

wherein an optimal solution to said decision model can optionally be determined by using integer programming.

11. The method of claim 9, wherein a decision model is used an input to said strategy optimization influence diagram.

12. The method of claim 10, wherein said step of formulating a given decision model as a nonlinear optimization problem further comprises the steps of:

specifying cases in said representative population;

constructing feasible actions for a decision for each case; and

specifying an objective function of said optimization.

13. The method of claim 0.12, wherein said step of specifying cases in said representative population comprises the step of:

selecting one of any of the following methods for specifying a set of cases;

using a set of cases from a previously encountered decision situation;

any of creating, designing, and specifying a set cases manually;

drawing samples from a joint distribution of decision key variables in said decision model using Monte Carlo methods;

wherein a joint probability distribution is defined over said decision key variables; and

enumerating all possible cases;

wherein a set of possible combinations of values of said decision keys is finite.

14. The method of claim 12, wherein said step of constructing feasible actions for a decision for each case comprises the step of:

notating a set of feasible actions for each case as A_i;

wherein A_i is a function of case-level constraints;

for each case c_l instantiating said decision keys E according to that case;

for each case-level constraint K_j computing a set A_ij of feasible decisions;

setting A_i to be a set of all actions in A that are feasible for all constraints, such that, A_i is the intersection of the sets A_ij;

computing a set A_ij of feasible decisions by selecting a method appropriate to a type of case-level constraint, wherein;

for constraints of type “

If q_j(E), then x in S_j”

computing a logical predicate q_j(E);

if q_j(E) is true, then setting A_ij to S_j;

if q_j(E) is false, then setting A_ij to A;

wherein all possible actions are feasible;

for constraints of “

h_j(E, x)<

d_j”

setting A_ij to an empty set for each alternative action a in A computing a value of h_j(E, a);

if h_j(E, a)<

d_j, then adding a to A_ij.

15. The method of claim 12, wherein said step of specifying an objective function of the optimization comprises the step of:

notating said objective function by F(C,X,W);

selecting a functional form for F(C,X,W), including any of;

a sum of some function f(c, x(c)) over all cases in C, or Sum_(c in C) {w(c)*f(c, x(c))}

a mean of some function f(c, x(c)) over all cases in C, or a ratio of Sum_(c in C) {w(c)*f(c, x(c))} to Sum_(c in C) {w(c)}

a mean or sum of some function f(c, x(c)) over a subset of cases in C; and

a sum of some function f2(c, x(c), m) over all cases in C for all possible instantiations m of portfolio variables in U, or Sum_(c in C, m in M) {P(U=m)* w(c)*f(c, x(c), m)}.

16. The method of claim 12, wherein said step of specifying an objective function of the optimization comprises the step of:

computing a component function f(c, x(c)), which is a sum of a value of value variables, evaluated at each case, for each case c by;

setting said decision keys in said decision model according to c;

then setting a decision according to x(c);

then evaluating all variables in a network; and

then evaluating a sum V_—

1+V_—

2+ . . . +V_N_V.

17. The method of claim 15, wherein a resulting nonlinear optimization problem is stated as:

selecting values for all variables x_i in X to maximize F(C,X,W);

subject to the constraints;

x_i is in A_i (for all i in 1 to N_C); and

G_j(C,X,W)<

=b_j (for all j in 1 to N_T); and

once formulated as a nonlinear optimization problem, optionally optimizing said decision model by using integer programming.

wherein a strategy table is output with a row for each case c_i in a representative population C, one column for each decision key of case c_i, and a column for an optimal action x*_j assigned to case c_i.

18. The method of claim 6, wherein said step of developing a strategy using induction on results of an optimization comprises the step of:

using any of induction techniques which include Bayes Net Learning, and CART (Classification and Regression Trees).

19. The method of claim 6, wherein said step of developing a strategy using induction on results of an optimization comprises the step of:

developing any of decision rules and strategies to express accurately how to assign at least one action to each case, based on its decision keys.

20. The method of claim 6, wherein said step of developing a strategy using induction on results of an optimization comprises the steps of:

finding a rule R defined over a target population, such that R(c_i) accurately predicts a value x*_i for cases c_i in a representative population C; and

using a strategy table to help develop said rule R.

21. The method of claim 20, wherein said rule R uses decision keys of c_i to either of compute or predict at least one assigned action.

22. The method of claim 20, wherein a most accurate decision rule is a rule for which r(c_i) is the same as x*_i, for each c_i in C.

23. A method for strategy design and strategy analysis, comprising the steps of:

providing one or more extensions to influence diagram methodology;

translating an influence diagram as a nonlinear optimization problem; and

induction after optimization to derive decision rules.

24. The method of claim 23, wherein said step of providing extensions to influence diagram methodology comprise any of the steps of:

effecting constrained optimization by placing constraints on an optimization in an influence diagram;

effecting dataset-based optimization over an explicitly specified set of cases which comprise a representative population, as well as over a set of cases implicitly specified by joint prior distributions of decision keys; and

mapping a decision model to a dataset file to map variables in an influence diagram to columns of a dataset.

25. The method of claim 23, wherein said step for translation of an influence diagram as a nonlinear optimization problem allows an influence diagram to contain continuous variables with complex functional forms, a specification of high-dimensional representative populations, and constraints.

26. The method of claim 23, wherein said step for induction derives simpler decision rules from many cases to allow for strategies that are more understandable, easier to edit, and easier to implement than an action provided in the raw optimization results.

27. An apparatus for using strategy optimization, comprising:

a strategy optimization influence diagram and a representative population for modeling a decision situation mathematically;

a mechanism for formatting said strategy optimization influence diagram as a nonlinear optimization problem over a representative population;

a mechanism for using nonlinear optimization techniques to assign at least one action to each case in a representative population;

a strategy table containing all cases in said representative population, along with at least one assigned action for each case;

a mechanism for applying induction techniques to said strategy table to derive a set of rules from data; and

a mechanism for operationalizing a set of rules derived by induction through a decision engine.

28. The apparatus of claim 27, wherein said influence diagram comprises any of a Bayesian network, Bayes'"'"' Net, and Bayesian model.

29. The apparatus of claim 27, wherein said mechanism for modeling a decision situation formulates and specifies a decision situation as a decision model, using a modeling language based on influence diagrams.

30. The apparatus of claim 29, wherein said modeling language comprises any of:

a mechanism for constraining optimization by associating a set of constraints with said decision model;

a mechanism for performing dataset-based optimization over an explicitly specified set of cases; and

a mechanism for mapping said decision model to a dataset file, wherein each decision key in said decision model is mapped with a column in a dataset.

31. The apparatus of claim 27, wherein said mechanism for formatting said strategy optimization influence diagram as a nonlinear optimization problem over a representative population formulates a nonlinear optimization problem that corresponds substantially exactly to a decision model specified in said modeling language;

wherein an optimal solution to said decision model can optionally be determined by using integer programming.

32. The apparatus of claim 31, wherein a decision model is used an input to said strategy optimization influence diagram.

33. The apparatus of claim 31, wherein said mechanism for formulating a given decision model as a nonlinear optimization problem further comprises:

a mechanism for specifying cases in said representative population;

a mechanism for constructing feasible actions for a decision for each case; and

a mechanism for specifying an objective function of said optimization.

34. The apparatus of claim 33, wherein said mechanism for specifying cases in said representative population comprises:

a mechanism for selecting one of any of the following mechanisms for specifying a set of cases;

a mechanism for using a set of cases from a previously encountered decision situation;

a mechanism for any of creating, designing, and specifying a set cases manually;

a mechanism for drawing samples from a joint distribution of decision key variables in said decision model using Monte Carlo methods;

wherein a joint probability distribution is defined over said decision key variables; and

a mechanism for enumerating all possible cases;

wherein a set of possible combinations of values of said decision keys is finite.

35. The apparatus of claim 33, wherein said mechanism for constructing feasible actions for a decision for each case comprises a mechanism for:

notating a set of feasible actions for each case as A_i;

wherein A_i is a function of case-level constraints;

for each case c_l instantiating said decision keys E according to that case;

for each case-level constraint K_j computing a set A_ij of feasible decisions;

setting A_i to be a set of all actions in A that are feasible for all constraints, such that, A_i is the intersection of the sets A_ij;

computing a set A_ij of feasible decisions by selecting a method appropriate to a type of case-level constraint, wherein;

for constraints of type “

If q_j(E), then x in S_j”

computing a logical predicate q_j(E);

if q_j(E) is true, then setting A_ij to S_j;

if q_j(E) is false, then setting A_ij to A;

wherein all possible actions are feasible;

for constraints of type “

h_j(E, x)<

d_j”

setting A_ij to an empty set for each alternative action a in A computing a value of h_j(E, a);

if h_j(E, a)<

d_j, then adding a to A_ij.

36. The apparatus of claim 33, wherein said mechanism for specifying an objective function of the optimization comprises a mechanism for:

notating said objective function by F(C,X,W);

selecting a functional form for F(C,X,W), including any of;

a sum of some function f(c, x(c)) over all cases in C, or Sum_(c in C) {w(c)*f(c, x(c))}

a mean of some function f(c, x(c)) over all cases in C, or a ratio of Sum_(c in C) {w(c)*f(c, x(c))} to Sum_(c in C) {w(c)}

a mean or sum of some function f(c, x(c)) over a subset of cases in C; and

a sum of some function f2(c, x(c), m) over all cases in C for all possible instantiations m of portfolio variables in U, or Sum_(c in C, m in M) {P(U=m)* w(c)*f(c, x(c), m)}.

37. The apparatus of claim 33, wherein said step of specifying an objective function of the optimization comprises:

a mechanism for computing a component function f(c, x(c)), which is a sum of a value of value variables, evaluated at each case, for each case c by;

setting said decision keys in said decision model according to c;

then setting a decision according to x(c);

then evaluating all variables in a network; and

then evaluating a sum V_—

1+V_—

2+ . . . +V_N_V.

38. The apparatus of claim 36, wherein a resulting nonlinear optimization problem is stated as:

selecting values for all variables x_i in X to maximize F(C,X,W);

subject to the constraints;

x_i is in A_i (for all i in 1 to N_C); and

G_j(C,X,W)<

=b_j (for all j in 1 to N_T); and

once formulated as a nonlinear optimization problem, optionally optimizing said decision model by using integer programming.

wherein a strategy table is output with a row for each case c_i in a representative population C, one column for each decision key of case c_i, and a column for an optimal action x*_i assigned to case c_i.

39. The apparatus of claim 27, wherein said mechanism for developing a strategy using induction on results of an optimization comprises:

a mechanism for using any of induction techniques which include Bayes Net Learning, and CART (Classification and Regression Trees).

40. The apparatus of claim 27, wherein said mechanism for developing a strategy using induction on results of an optimization comprises:

a mechanism for developing any of decision rules and strategies to express accurately how to assign at least one action to each case, based on its decision keys.

41. The apparatus of claim 27, wherein said mechanism for developing a strategy using induction on results of an optimization comprises:

a mechanism for finding a rule R defined over a target population, such that R(c_i) accurately predicts a value x*_i for cases c_i in a representative population C; and

a strategy table to help develop said rule R.

42. The apparatus of claim 41, wherein said rule R uses decision keys of c_i to either of compute or predict at least one assigned action.

43. The apparatus of claim 41, wherein a most accurate decision rule is a rule for which r(c_i) is the same as x*_i, for each c_i in C.

44. An apparatus for using strategy optimization, comprising:

a strategy optimization influence diagram and a representative population for modeling a decision situation mathematically; and

a mechanism for formatting said strategy optimization influence diagram as a nonlinear optimization problem over a representative population.

45. The apparatus of claim 44, wherein said influence diagram comprises any of a Bayesian network, Bayes'"'"' Net, and Bayesian model 46. An apparatus for using strategy optimization, comprising:

a mechanism for using nonlinear optimization techniques to assign at least one action to each case in a representative population; and

a strategy table containing all cases in said representative population, along with at least one assigned action for each case.

47. An apparatus for using strategy optimization, comprising:

a mechanism for applying induction techniques to a strategy table to derive a set of rules from data; and

a mechanism for operationalizing a set of rules-derived by induction through a decision engine.

48. A method for using strategy optimization, comprising the steps of:

providing a strategy optimization influence diagram and a representative population for modeling a decision situation mathematically; and

formatting said strategy optimization influence diagram as a nonlinear optimization problem over a representative population.

49. The method of claim 48, wherein said influence diagram comprises any of a Bayesian network, Bayes'"'"' Net, and Bayesian model.

50. A method for using strategy optimization, comprising the steps of:

using nonlinear optimization techniques to assign at least one action to each case in a representative population; and

providing a strategy table containing all cases in said representative population, along with at least one assigned action for each case.

51. A method for using strategy optimization, comprising the steps of:

applying induction techniques to a strategy table to derive a set of rules from data; and

operationalizing a set of rules derived by induction through a decision engine.