Systems, methods and circuits for learning of relation-based networks

• US 8,341,097 B2
• Filed: 01/29/2010
• Issued: 12/25/2012
• Est. Priority Date: 01/30/2009
• Status: Expired due to Fees

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Inventors: Meng, Teresa H., Wong, Wing H., Asadi Bani, Narges
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US12/696,317
• Publication Number:
  US 20100198761A1
• Time in Patent Office: 1,061 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Circuits, devices and methods for processing learning networks are implemented using a variety of methods and devices. One example involves a circuit-implemented method to identify a relationship of objects in a set of objects. Local scores are generated for the object and possible parents. The local scores indicate relationship strength between object and parent. The results are stored in a memory. A state-machine circuit is used to perform sampling and searching of the parent sets for each data node. The local scores are used to encode orderings of the parent. An algorithm is executed that uses the encoded possible orderings and a random variable to generate and score a current order and a proposed order of the possible parent sets. The proposed orders are accepted or rejected based on probability rules applied to the scores for the current and proposed orders. Structures are sampled to assess a Bayesian-based relationship.

Claims

1. A system for computations to learn the relationships and patterns in a set of observed objects, the system comprising:

circuitry configured to

implement parallel and sequential implementation versions of an algorithm for search and sampling of structures; and

perform two dimensional encoding of ordering between the variables to facilitate efficient computations, fixed point representation of values for efficient computation.

2. The system of claim 1, wherein the circuitry includes a processor and a tangible recordable medium storing instructions that when executed by the processor result in the implementation of the parallel and sequential implementation versions of an algorithm for search and sampling of structures and the performance of two dimensional encoding of ordering between the variables to facilitate efficient computations, fixed point representation of values for efficient computation.

3. The system of claim 1, wherein the circuitry includes hardware configured and arranged to implement the parallel and sequential implementation versions of an algorithm for search and sampling of structures;

and to perform two dimensional encoding of ordering between the variables to facilitate efficient computations, fixed point representation of values for efficient computation.

4. The system of claim 1, wherein the circuitry is further configured to

generate local scores for each object and possible parent sets of that object, wherein the local scores are indicative of the strength of the relationship between each object and a parent set;

and

sample structures derived from the generated local scores for each object to assess and, indicating therefrom, a Bayesian-based relationship.

5. A circuit-implemented method to identify at least one pattern, or relationship, of objects in a set of objects, the method comprising:

pre-processing the set of objects by

operating a logic circuit to generate local scores for each object and possible parent sets of that object, wherein the local scores are indicative of the strength of the relationship between each object and a parent set, and

storing the local scores and the possible parent sets in a memory circuit that is configured and arranged to provide, for each of the data nodes, access to each of the possible parent sets and the local scores;

after pre-processing the set of objects, while accessing the stored local scores and possible parent sets, using a state-machine circuit to perform sampling and searching of the parent sets for each data node, including

using the local scores to encode possible orderings of the parent sets,

executing an algorithm, that uses the encoded possible orderings and a random variable, for generating and scoring a current order and a proposed order of the possible parent sets, and

choosing to accept or reject the proposed orders based on a set of probability rules applied to the scores for the current and proposed orders; and

sampling structures derived from the accepted proposed orders to assess and, indicating therefrom, a Bayesian-based relationship.

6. The method of claim 5, wherein the step of pre-processing further includes the step of concurrently operating similarly-constructed logic circuits, respectively, to generate local scores of possible parent sets for each of the objects.

7. The method of claim 6, wherein the similarly-constructed logic circuits are FPGA-based circuits.

8. The method of claim 5, wherein the step of pre-processing is performed only once for the step of sampling structures from the accepted proposed orders.

9. The method of claim 5, wherein the algorithm is a based on MCMC sampling algorithm and wherein executing the algorithm includes learning orders in response to choosing to accept or reject the proposed orders.

10. The method of claim 9, wherein the set of probability rules includes rules indicating that a chain of the proposed orders, subjected to the algorithm, will tend to converge to a posterior probability in steady state.

11. The method of claim 5, wherein the state-machine circuit is operated to randomly walk through possible orders.

12. The method of claim 11, wherein the step of using the state-machine circuit to walk through possible orders includes applying a random change to previously-encoded possible orderings of the parent sets.

13. The method of claim 5, further including two dimensional encoding of ordering between the variables to permit more efficient computations, fixed point representation of values for efficient computation.

14. A system to identify at least one pattern, or relationship, of data nodes in a set of data nodes, the system comprising:

a pre-processing logic circuit configured and arranged to

generate local scores for each object and possible parent sets of that object, wherein the local scores are indicative of the strength the relationship between each object and a parent set, and

store the local scores and the possible parent sets in a memory circuit that is configured and arranged to provide, for each of the data nodes, access to each of the possible parent sets and the local scores;

a state-machine circuit configured and arranged to, after pre-processing the set of objects and while accessing the stored local scores and possible parent sets, perform sampling and searching of the parent sets for each data node including

using the local scores to encode possible orderings of the parent sets,

executing an algorithm, that uses the encoded possible orderings and a random variable, for generating and scoring a current order and a proposed order of the possible parent sets, and

choosing to accept or reject the proposed orders based on a set of probability rules applied to the scores for the current and proposed orders; and

a processing circuit configured and arranged to sample structures derived from the accepted proposed orders to assess and, indicating therefrom, a Bayesian-based relationship.

15. The system of claim 14, wherein the pre-processing logic circuit is further configured to concurrently operate similarly-constructed logic circuits, respectively, and to generate local scores of possible parent sets for each of the objects.

16. The system of claim 15, wherein the similarly-constructed logic circuits are FPGA-based circuits.

17. The system of claim 14, wherein the pre-processing logic circuit is further configured to performed the pre-processing steps only once for the step of sampling structures from the accepted proposed orders.

18. The system of claim 14, wherein the algorithm is a based on MCMC sampling algorithm and wherein executing the algorithm includes learning orders in response to choosing to accept or reject the proposed orders.

19. The system of claim 14, wherein the set of probability rules includes rules indicating that a chain of the proposed orders, subjected to the algorithm, will tend to converge to a posterior probability in steady state.

20. The system of claim 14, wherein the state-machine circuit is operated to randomly walk through possible orders.

21. The system of claim 20, wherein using the state-machine circuit to walk through possible orders includes applying a random change to previously-encoded possible orderings of the parent sets.

22. The system of claim 14, wherein the system is further configured to implement two dimensional encoding of ordering between the variables in a manner that provides efficient computations and fixed point representation of values for efficient computation.