4
$\begingroup$

I look for an efficient way to implement a Belief Propagation in Pairwise Markov Random Field.

Each node is a binary random variable, and the unary potential function is

nodePotential[v_] := Piecewise[{{a, v == 1}, {1-a, v == -1}}]

The pairwise potential function is

pairwisePotential[p_] := {{p, 1 - p}, {1 - p, p}}

I have a data structure which contains the unary potential of each node:

nodePot=Association@Map[# -> {0.3, 0.7} &, VertexList@g1]

And data structure which contains the pairwise potential is a matrix

edgeSimilarity=AdjacencyMatrix[g1]*0.6; 

Note that I deal with different unary/pairwise potential, but for simplifying the question, I am using here homogeneous.

With the following function, I calculate the LBP

LBP[data_, index_] := 
 Module[{totalPo, nonZeroPosition, nonZeroValues, nzp, nzv, newP, edP, spNZV},
  totalPo = Total@data["NonzeroValues"];
  nonZeroPosition = data["NonzeroPositions"];
  nonZeroValues = data["NonzeroValues"];
  newP = Thread[List[Flatten[nonZeroPosition], index]];
  edP = edgeSimilarity[[index]]["NonzeroValues"];
  edP = DeleteCases[edP, 0.0];
  edP = pairwisePotential[#] & /@ edP;
  edP = (Exp[totalPo - #] & /@ nonZeroValues)*edP;
  nzv = (nodePot[index].#) & /@ Flatten[edP, 1];
  {newP, nzv}
  ]

I work in log domain to prevent the numerical issues in dense graph

newMessageMatrix[data_] := Module[{res, positions, values},
  res = Transpose@data;
  positions = Flatten[Join [{{{{1, 1}}}}, Transpose[{res[[1]], res[[1]]}]], 2];
  values = Log[Flatten@Join[{1.0000000000001}, res[[2]]]];
   Chop@With[{spopt = SystemOptions["SparseArrayOptions"]}, 
    Internal`WithLocalSettings[
     SetSystemOptions["SparseArrayOptions" -> {"TreatRepeatedEntries" -> List}], 
     SparseArray[positions -> values, Dimensions[s], 0], 
     SetSystemOptions[spopt]]]
    ]

s = AdjacencyMatrix@g1;
sT = 2*s;

Each iteration of LBP is

valuesAndPositions = LBP[sT[[#]], #] & /@VertexList[g1];
resMat = newMessageMatrix[valuesAndPositions];

Any suggestion how on speed up the calculation and reduce memory use

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.