Method and apparatus for improving the speed of belief propagation
US7606420B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Oct 31, 2005 |
| Grant date | Oct 20, 2009 |
| Priority date | — |
| Expiry date | Dec 21, 2027 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F18/29
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
One embodiment of the present invention provides a system that efficiently performs a belief-propagation (BP) operation. During this process, for each node i in a BP graph, the system iteratively performs the following operations. First, the system receives incoming messages mji at node i for all adjacent nodes j. Next, the system calculates the full product Pi of all incoming messages mji. The system then produces an outgoing message mij from node i to node j by, computing a partial product Pij of all incoming messages to node i except for the message from node j by dividing the Pi by the incoming message from node j. The system then combines Pij with a data function for node i and a smoothness function between node i and node j to produce outgoing message mij. Finally the system communicates outgoing message mij to node j. This system improves computational efficiency over existing BP techniques because computing the full product Pi first and then dividing by individual incoming messages to produce each partial product is faster than computing each partial product separately.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.