Belief Propagation in GraphLab Create

As you may know I really like probabilistic graphical models, and my PhD Thesis was focused on Gaussian Belief Propagation. My Colleauge Alon Palombo have recently implemented a graphical model inference toolkit on top of GraphLab Create. We are looking for academic researchers or companies who would like to try it out.

Here is a quick example for graph coloring using BP:

2-color a cube

In [2]:

cube = gl.SGraph()

​

edge_potential = [

                    [1e-08, 1], 

                    [1, 1e-08], 

                 ]

​

variables = gl.SFrame({'var' : range(8),

                       'prior' : [[1, 0]] + [[1, 1]] * 7})

​

cube = cube.add_vertices(variables, 'var')

​

edges = gl.SFrame({'src' : [0, 0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 6],

                   'dst' : [1, 2, 4, 3, 5, 3, 6, 7, 5, 6, 7, 7],

                   'potential' : [edge_potential] * 12})

​

cube = cube.add_edges(edges, src_field='src', dst_field='dst')

cube.show(vlabel='__id')

In [3]:

coloring = bp.belief_propagation(graph=cube,

                                 prior='prior',

                                 edge_potential='potential',

                                 num_iterations=10,

                                 method='sum',

                                 convergence_threshold=0.01).unpack('marginal')

In [4]:

coloring['color'] = coloring.apply(lambda x: x['marginal.0'] < x['marginal.1'])

In [5]:

Out[5]:

__id	marginal.0	marginal.1	color
5	1.0	1.00000003e-24	0
7	1.00000003e-24	1.0	1
0	1.0	0.0	0
2	1.00000002e-24	1.0	1
6	1.0	1.00000003e-24	0
3	1.0	1.00000003e-24	0
1	1.00000002e-24	1.0	1
4	1.00000002e-24	1.0	1

[8 rows x 4 columns]

In [7]:

cube.show(vlabel='__id', highlight=cube.vertices[coloring['color']]['__id'])

Another cool example from Pearl's paper:

Burglar Alarm Example

What is the probability that there is a burglary given that Ali calls? 0.0162 (slide 10)

In [14]:

#Priors

pr_bur = [0.001, 0.999]

pr_earth = [0.002, 0.998]

pr_bur_earth = [1, 1, 1, 1]

pr_alarm = [1, 1]

pr_ali = [1, 0] #Ali calls

pr_veli = [1, 1]

​

#Edge potentials

Pbeb = [[1, 0],

        [1, 0],

        [0, 1],

        [0, 1]]

​

Pbee = [[1, 0],

        [0, 1],

        [1, 0],

        [0, 1]]

​

Pabe = [[0.95, 0.94, 0.29, 0.001],

        [0.05, 0.06, 0.71, 0.999]]

​

Paa  = [[0.9, 0.05],

        [0.1, 0.95]]

​

Pva  = [[0.7, 0.01],

        [0.3, 0.99]]

​

vertices = gl.SFrame({'id' : ['Burglary', 'Earthquake', 'B_E', 'Alarm', 'Ali Calls', 'Veli Calls'],

                      'prior' : [pr_bur, pr_earth, pr_bur_earth, pr_alarm, pr_ali, pr_veli]})

​

edges = gl.SFrame({'src_id' : ['Burglary', 'Earthquake', 'B_E', 'Alarm', 'Alarm'],

                   'dst_id' : ['B_E', 'B_E', 'Alarm', 'Ali Calls', 'Veli Calls'],

                   'potential' : [Pbeb, Pbee, Pabe, Paa, Pva]})

​

g = gl.SGraph()

g = g.add_vertices(vertices, 'id')

g = g.add_edges(edges,src_field='src_id', dst_field='dst_id')

g.show(vlabel='__id', arrows=True)

In [15]:

marginals = bp.belief_propagation(graph=g,

                                  prior='prior',

                                  edge_potential='potential',

                                  num_iterations=10,

                                  method='sum',

                                  convergence_threshold=0.01).unpack('marginal')

​

#Filtering out the dummy variable's values to print nicely

marginals[['__id', 'marginal.0', 'marginal.1']].filter_by(['B_E'], '__id', exclude=True)

Out[15]:

__id	marginal.0	marginal.1
Veli Calls	0.0399720211419	0.960027978858
Ali Calls	1.0	0.0
Alarm	0.0434377117999	0.9565622882
Burglary	0.0162837299468	0.983716270053
Earthquake	0.0113949687738	0.988605031226

[? rows x 3 columns]
Note: Only the head of the SFrame is printed. This SFrame is lazily evaluated.
You can use len(sf) to force materialization.

What about if Veli also calls right after Ali hangs up? (0.29)

In [16]:

pr_veli = [1, 0] #Veli calls

vertices = gl.SFrame({'id' : ['Burglary', 'Earthquake', 'B_E', 'Alarm', 'Ali Calls', 'Veli Calls'],

                      'prior' : [pr_bur, pr_earth, pr_bur_earth, pr_alarm, pr_ali, pr_veli]})

​

edges = gl.SFrame({'src_id' : ['Burglary', 'Earthquake', 'B_E', 'Alarm', 'Alarm'],

                   'dst_id' : ['B_E', 'B_E', 'Alarm', 'Ali Calls', 'Veli Calls'],

                   'potential' : [Pbeb, Pbee, Pabe, Paa, Pva]})

​

g = gl.SGraph()

g = g.add_vertices(vertices, 'id')

g = g.add_edges(edges,src_field='src_id', dst_field='dst_id')

In [17]:

marginals = bp.belief_propagation(graph=g,

                                  prior='prior',

                                  edge_potential='potential',

                                  num_iterations=10,

                                  method='sum',

                                  convergence_threshold=0.01).unpack('marginal')

​

#Filtering out the dummy variable's values to print nicely

marginals[['__id', 'marginal.0', 'marginal.1']].filter_by(['B_E'], '__id', exclude=True)

PROGRESS: Iteration 1: Sum of l2 change in messages 6.64879
PROGRESS: Iteration 2: Sum of l2 change in messages 7.15545
PROGRESS: Iteration 3: Sum of l2 change in messages 0

Out[17]:

__id	marginal.0	marginal.1
Veli Calls	1.0	0.0
Ali Calls	1.0	0.0
Alarm	0.760692038863	0.239307961137
Burglary	0.284171835364	0.715828164636
Earthquake	0.176066838405	0.823933161595

[? rows x 3 columns]
Note: Only the head of the SFrame is printed. This SFrame is lazily evaluated.
You can use len(sf) to force materialization.