Saturday, December 12, 2015

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]:
__idmarginal.0marginal.1color
51.01.00000003e-240
71.00000003e-241.01
01.00.00
21.00000002e-241.01
61.01.00000003e-240
31.01.00000003e-240
11.00000002e-241.01
41.00000002e-241.01
[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]:
__idmarginal.0marginal.1
Veli Calls0.03997202114190.960027978858
Ali Calls1.00.0
Alarm0.04343771179990.9565622882
Burglary0.01628372994680.983716270053
Earthquake0.01139496877380.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]:
__idmarginal.0marginal.1
Veli Calls1.00.0
Ali Calls1.00.0
Alarm0.7606920388630.239307961137
Burglary0.2841718353640.715828164636
Earthquake0.1760668384050.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.

No comments:

Post a Comment