Posted in Algorithm, Statitics

Loopy BP: an easy implementation on Pregel Model

Pregel: Message Passing.

Focus on the process, no matter each vertex computation.

Steps [1]:

(this part was referenced from a blog)

A node passes a message to an adjacent node only when it has received all incoming messages, excluding the message from the destination node to itself. Below shows an example of a message being passed from  x1 to x2 .

Node x1  waits for messages from nodes A,B,C,D before sending its message to . As a reminder, it does not send the message from  x2->x1 back to x1 (no feedback) .

An easy version of algo given by me:

Input: Graph g, number of iteration n.

Output: the “best” label for each vertex.

_________________________________________

function LoopyBP (Graph g, int n):

for each vertex in Graph g:

    initialise message.

for each edge in Graph g:

    initialise conditional probability.

// to avoid wait-forever problem ( a random state can be chosen, intend to testing)

for n times of iteration:

    (simultaneously) pass message to the peer node(?)

    calculate dot-product

    find the best label as the belief

_________________________________________

Five key questions

1. message init

    for each vertex, we can have multiple states with a random probability of each, but sum up to 1(normalisation).

etc. (0.3,0.6,0.1)

2. edge init

    for each edge, init, same as question 1.

3. message update

    when sending message, if A->B

    message (A->B) =( Neighbours exclude B Sum-up in Vertex A )* Edge (A->B)

4. calculate belief

    after received every message from peer vertex,

    choose the best label for the node, marked as the belief

5. loops

    do BP for many times.

A question to think about(difficult):

How to synchronize? A vertex can only send a message to another one when it receives every msg exclude this one. How to start the whole process?

[1]http://nghiaho.com/?page_id=1366

Author:

Keep calm and update blog.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s