Valuation-based learning system

• US 8,032,467 B1
• Filed: 05/31/2008
• Issued: 10/04/2011
• Est. Priority Date: 05/31/2008
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Shu, David, Chen, Yang, Jiang, Qin
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US12/156,447
• Time in Patent Office: 1,221 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

The present invention relates to a valuation-based learning system. The system is configured to receive a plurality of inputs, each input being input evidence corresponding to a variable in a Dempster-Shafer Reasoning System. The Dempster-Shafer Reasoning System is a network of interconnected nodes, with each node representing a variable that is representative of a characteristic of a problem domain. A discount weight is then optimized for assigning to each of the inputs. A basic probability assignment (bpa) is generated using the Dempster-Shafer Reasoning System, and where the bpa is an output for use in determining a solution of the problem domain. Finally, a solution to the problem domain is determined using the bpa.

Claims

1. A method for learning in a valuation-based learning system, comprising an act of manipulating a computer to perform acts of:

receiving a plurality of inputs, each input being input evidence corresponding to a variable in a Dempster-Shafer Reasoning System, wherein the Dempster-Shafer Reasoning System is a network of interconnected nodes, with each node being representative of a characteristic of a problem domain;

optimizing a discount weight for assigning to each of the inputs;

generating a basic probability assignment (bpa) using the Dempster-Shafer Reasoning System, and where the bpa is an output for use in determining a solution of the problem domain;

determining a solution to the problem domain using the bpa; and

providing the solution to a user.

2. A method as set forth in claim 1, further comprising an act of manipulating a computer to perform acts of:

receiving a known truth corresponding to a variable having a probability distribution, the known truth having characteristics;

comparing the characteristics of the known truth to the probability distribution to generate an error; and

updating the weights assigned to the inputs to minimize the error.

3. A method as set forth in claim 1, wherein the act of optimizing a discount weight for assigning to each of the inputs further comprises acts of:

identifying a set of variables in the Dempster-Shafer Reasoning System, where each variable in the set has at least one input basic probability assignment (bpa);

identifying at least one output variable, the output variable having output bpa corresponding to the input bpa;

defining a gradient of an objective function in terms of a discounting weight vector, an output bpa, and a partial derivative of the output bpa with respect to the discounting weight vector;

calculating an output bpa for each variable with its input bpa, without discounting, and storing the result;

recalculating the output bpa for each variable without applying its input bpa, and storing the result;

using the results obtained in the acts of calculating and recalculating to redefine the gradient according to the act of defining the gradient;

updating the discounting weight vector; and

repeating the acts of defining through updating until convergence of the discounting weight vector, and where upon convergence, the weights reflected in the discounting weight vector are optimal weights for use in the act of optimizing a weight to assign to each of the inputs.

4. A method as set forth in claim 3, wherein in the act of defining a gradient of an objective function in terms of a discounting weight vector, the objective function is based on the combined bpa on a variable Xε

U, with variable frame Θ

_X, and is defined as;

5. A method as set forth in claim 1, wherein the act of optimizing a discount weight for assigning to each of the inputs further comprises acts of:

identifying a set of variables in the Dempster-Shafer Reasoning System, where each variable in the set has at least one input basic probability assignment (bpa);

identifying at least one output variable, the output variable having output bpa corresponding to the input bpa;

defining a gradient of an objective function in terms of a discounting weight vector, an output bpa, and a partial derivative of the output bpa with respect to the discounting weight vector;

at an initial time, calculating the output bpa without an input bpa being applied, and storing the result;

for a next input at time k, calculating an output bpa with the input bpa being applied without discounting, and storing the result;

redefining the gradient according to the act of defining the gradient, using the results obtained, at a time and a previous time, in the act of calculating an output bpa with the input bpa being applied;

updating the discounting weight factor; and

repeating the operations of calculating an output bpa with the input bpa being applied through updating the discounting weight factor until convergence of the discounting weight factor or until the input is exhausted.

6. A method as set forth in claim 5, wherein in the act of defining a gradient of an objective function in terms of a discounting weight vector, the objective function is based on the combined bpa on a variable Xε

U, with variable frame Θ

_X, and is defined as;

7. A valuation-based learning system, the system having a processor configured to perform operations of:

receiving a plurality of inputs, each input being input evidence corresponding to a variable in a Dempster-Shafer Reasoning System, wherein the Dempster-Shafer Reasoning System is a network of interconnected nodes, with each node being representative of a characteristic of a problem domain;

optimizing a discount weight for assigning to each of the inputs;

generating a basic probability assignment (bpa) using the Dempster-Shafer Reasoning System, and where the bpa is an output for use in determining a solution of the problem domain;

determining a solution to the problem domain using the bpa; and

providing the solution to a user.

8. A system as set forth in claim 7, wherein the processor is further configured to perform operations of:

receiving a known truth corresponding to a variable having a probability distribution, the known truth having characteristics;

comparing the characteristics of the known truth to the probability distribution to generate an error; and

updating the weights assigned to the inputs to minimize the error.

9. A system as set forth in claim 7, wherein in the operation of optimizing a discount weight for assigning to each of the inputs, the processor is further configured to perform operations of:

identifying a set of variables in the Dempster-Shafer Reasoning System, where each variable in the set has at least one input basic probability assignment (bpa);

identifying at least one output variable, the output variable having output bpa corresponding to the input bpa;

defining a gradient of an objective function in terms of a discounting weight vector, an output bpa, and a partial derivative of the output bpa with respect to the discounting weight vector;

calculating an output bpa for each variable with its input bpa, without discounting, and storing the result;

recalculating the output bpa for each variable without applying its input bpa, and storing the result;

using the results obtained in the acts of calculating and recalculating to redefine the gradient according to the act of defining the gradient;

updating the discounting weight vector; and

repeating the acts of defining through updating until convergence of the discounting weight vector, and where upon convergence, the weights reflected in the discounting weight vector are optimal weights for use in the act of optimizing a weight to assign to each of the inputs.

10. A system as set forth in claim 9, wherein in defining a gradient of an objective function in terms of a discounting weight vector, the objective function is based on the combined bpa on a variable Xε

U, with variable frame Θ

_X, and is defined as;

11. A system as set forth in claim 7, wherein in the operation of optimizing a discount weight for assigning to each of the inputs, the processor is further configured to perform operations of:

identifying a set of variables in the Dempster-Shafer Reasoning System, where each variable in the set has at least one input basic probability assignment (bpa);

identifying at least one output variable, the output variable having output bpa corresponding to the input bpa;

defining a gradient of an objective function in terms of a discounting weight vector, an output bpa, and a partial derivative of the output bpa with respect to the discounting weight vector;

at an initial time, calculating the output bpa without an input bpa being applied, and storing the result;

for a next input at time k, calculating an output bpa with the input bpa being applied without discounting, and storing the result;

redefining the gradient according to the operation of defining the gradient, using the results obtained, at a time and a previous time, in the operation of calculating an output bpa with the input bpa being applied;

updating the discounting weight factor; and

repeating the operations of calculating an output bpa with the input bpa being applied through updating the discounting weight factor until convergence of the discounting weight factor or until the input is exhausted.

12. A system as set forth in claim 11, wherein in defining a gradient of an objective function in terms of a discounting weight vector, the objective function is based on the combined bpa on a variable Xε

U, with variable frame Θ

_X and is defined as;

13. A computer program product for operating a valuation-based learning system, the computer program product comprising computer-readable instruction means stored on a computer-readable medium that are executable by a computer for causing the computer to perform operations of:

receiving a plurality of inputs, each input being input evidence corresponding to a variable in a Dempster-Shafer Reasoning System, wherein the Dempster-Shafer Reasoning System is a network of interconnected nodes, with each node being representative of a characteristic of a problem domain;

optimizing a discount weight for assigning to each of the inputs;

generating a basic probability assignment (bpa) using the Dempster-Shafer Reasoning System, and where the bpa is an output for use in determining a solution of the problem domain;

determining a solution to the problem domain using the bpa; and

providing the solution to a user.

14. A computer program product as set forth in claim 13, further comprising instruction means for causing a computer to perform operations of:

receiving a known truth corresponding to a variable having a probability distribution, the known truth having characteristics;

comparing the characteristics of the known truth to the probability distribution to generate an error; and

updating the weights assigned to the inputs to minimize the error.

15. A computer program product as set forth in claim 13, further comprising instruction means for causing a computer to perform operations of:

identifying a set of variables in the Dempster-Shafer Reasoning System, where each variable in the set has at least one input basic probability assignment (bpa);

identifying at least one output variable, the output variable having output bpa corresponding to the input bpa;

defining a gradient of an objective function in terms of a discounting weight vector, an output bpa, and a partial derivative of the output bpa with respect to the discounting weight vector;

calculating an output bpa for each variable with its input bpa, without discounting, and storing the result;

recalculating the output bpa for each variable without applying its input bpa, and storing the result;

using the results obtained in the acts of calculating and recalculating to redefine the gradient according to the act of defining the gradient;

updating the discounting weight vector; and

repeating the acts of defining through updating until convergence of the discounting weight vector, and where upon convergence, the weights reflected in the discounting weight vector are optimal weights for use in the act of optimizing a weight to assign to each of the inputs.

16. A computer program product as set forth in claim 15, wherein in defining a gradient of an objective function in terms of a discounting weight vector, the objective function is based on the combined bpa on a variable Xε

U, with variable frame Θ

_X, and is defined as;

17. A computer program product as set forth in claim 13, further comprising instruction means for causing a computer to perform operations of:

identifying a set of variables in the Dempster-Shafer Reasoning System, where each variable in the set has at least one input basic probability assignment (bpa);

identifying at least one output variable, the output variable having output bpa corresponding to the input bpa;

defining a gradient of an objective function in terms of a discounting weight vector, an output bpa, and a partial derivative of the output bpa with respect to the discounting weight vector;

at an initial time, calculating the output bpa without an input bpa being applied, and storing the result;

for a next input at time k, calculating an output bpa with the input bpa being applied without discounting, and storing the result;

redefining the gradient according to the operation of defining the gradient, using the results obtained, at a time and a previous time, in the operation of calculating an output bpa with the input bpa being applied;

updating the discounting weight factor; and

repeating the operations of calculating an output bpa with the input bpa being applied through updating the discounting weight factor until convergence of the discounting weight factor or until the input is exhausted.

18. A system as set forth in claim 17, wherein in defining a gradient of an objective function in terms of a discounting weight vector, the objective function is based on the combined bpa on a variable Xε

U, with variable frame Θ

_X, and is defined as;