Analog computation using numerical representations with uncertainty

• US 20100223225A1
• Filed: 03/02/2010
• Published: 09/02/2010
• Est. Priority Date: 03/02/2009
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Lyric Semiconductor, Inc. (Analog Devices, Inc.)
• Inventors: Hershey, Shawn, Vigoda, Benjamin, Bradley, William, Bernstein, Jeffrey
• Granted Patent: US 8,458,114 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Some general aspects relate to systems and methods of analog computation using numerical representation with uncertainty. For example, a specification of a group of variables is accepted, with each variable having a set of at least N possible values. The group of variables satisfies a set of one or more constraints, and each variable is specified as a decomposition into a group of constituents, with each constituent having a set of M (e.g., M<N) possible constituent values that can be determined based on the variable values. The method also includes forming a specification for configuring a computing device that implements a network representation of the constraints based on the specification of the group of variables. The network representation includes a first set of nodes corresponding to the groups of constituents, a second set of nodes corresponding to the set of constraints, and interconnections between the first and the second sets of nodes for passing continuous-valued data.

Claims

1. A method comprising:

accepting a specification of a plurality of variables, each variable having a set of at least N possible values, wherein the plurality of variables satisfy a set of one or more constraints, and each variable is specified as a decomposition into a plurality of constituents with each constituent having a set of M possible constituent values that can be determined based on the variable values;

forming a specification for configuring a computing device that implements a network representation of the constraints based on the specification of the plurality of variables, wherein the network representation includes a first set of nodes corresponding to the pluralities of constituents, a second set of nodes corresponding to the set of constraints, and interconnections between the first and the second sets of nodes for passing continuous-valued data; and

wherein the computing device configured according to said specification is operable to;

accept a first set of quantities each characterizing a degree of association of one constituent of one of the plurality of variables with one of the M possible constituent values; and

determine a second set of quantities each characterizing a degree of association of one constituent of one of the plurality of variables with one of the M possible constituent values by passing the first set of quantities and intermediate data along the interconnections in the network representation.

2. The method of claim 1, wherein said specification for the computing device includes an analog circuit specification.

3. The method of claim 2, wherein said analog circuit specification includes a discrete-time analog circuit specification.

4. The method of claim 1, wherein said specification for the computing device includes software instructions for execution on a processor.

5. The method of claim 1, wherein the set of constraints includes a first set of arithmetic constraints.

6. The method of claim 1, wherein the set of constraints includes a second set of logical constraints.

7. The method of claim 1, wherein the specification of the plurality of variables represents a compressed representation of a first specification of the plurality of variables.

8. The method of claim 1, wherein the N is greater than M.

9. The method of claim 1, further comprising forming the specification of the plurality of variables each as a decomposition into a plurality of constituents based on a first specification of the plurality of variables.

10. The method of claim 9, wherein the first specification of the plurality of variables includes a probability distribution representation of the plurality of variables.

11. The method of claim 10, wherein forming the specification of the plurality of variables each as a decomposition into a plurality of constituents includes:

applying binary decomposition to the probability distribution representation of the plurality of variables.

12. The method of claim 10, wherein forming the specification of the plurality of variables each as a decomposition into a plurality of constituents includes:

applying a Fourier transform to the probability distribution representation of the plurality of variables.

13. The method of claim 10, wherein the probability distribution representation of the plurality of variables includes quantities characterizing a degree of association of each one of at least some of the variables with the one or more of the at least N possible values.

14. The method of claim 1, wherein the degree of association of one constituent of one of the plurality of variables with one of the M possible constituent values is represented in the probability domain.

15. The method of claim 1, wherein the degree of association of one constituent of one of the plurality of variables with one of the M possible constituent values is represented in the logarithmic domain.

16. A method comprising:

accepting a first set of quantities, each associated with one of M possible constituent values of a constituent of one of a plurality of input variables, each variable having a set of at least N possible values;

providing signals representing the first set of quantities to computing circuitry implementing a network representation of a set of constraints on the input variables, the network representation including a first set of nodes each corresponding to one of a plurality of constituents of a respective input variable, a second set of nodes corresponding to the set of constraints, and interconnections between the first and the second sets of nodes for passing continuous-valued data;

accepting, from the computing circuitry, signals representing a second set of quantities, each associated with one of M possible constituent values of a constituent of one input variable.

17. The method of claim 16, further comprising:

determining the first set of quantities from a first specification of the plurality of input variables, the first specification including quantities characterizing a degree of association of each of at least some input variables with a different one of the at least N possible values.

18. The method of claim 16, further comprising:

according to the signals representing the second quantities, generating a set of output signals, each representing a degree of association of one of the plurality of input variables with a corresponding one of the at least N possible values.

19. The method of claim 16, wherein the computing circuitry includes analog circuits.

20. The method of claim 19, wherein the analog circuits include a clocked analog circuit.

21. The method of claim 20, wherein the clocked analog circuit includes soft logic gates for processing continuous-valued signals.

22. The method of claim 21, wherein the soft logic gates include one or more of soft Equal gates, soft XOR gates, soft AND gates, soft OR gates.

23. The method of claim 16, wherein the computing circuitry includes a processor configured by software instructions.

24. A computing device comprising:

computing circuitry for applying a network representation of a set of constraints on a plurality of input variables, each input variable having a set of at least N possible values, wherein the network representation includes a first set of nodes each corresponding to one of a plurality of constituents of a respective input variable, a second set of nodes corresponding to the set of constraints, and interconnections between the first and the second sets of nodes for passing data;

an input processor for forming signals representing a first set of quantities, each quantity being associated with one of M possible constituent values of a constituent of one input variable, and for providing the formed signals to the computing circuitry; and

an output processor for accepting signals generated by the computing circuitry representing a second set of quantities, each quantity being associated with one of the M possible constituent values of a constituent of one input variable.

25. The computing device of claim 24, wherein the computing circuitry is configured according to the network representation.

26. The computing device of claim 24, wherein the computing circuitry is configurable according to the network representation.

27. The computing device of claim 26, wherein the computing circuitry is operable to:

accept a specification of the network representation of the set of constraints; and

configure the circuitry to implement the network representation of the set of constraints according to the specification of the network representation.