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


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"]}, 
     SetSystemOptions["SparseArrayOptions" -> {"TreatRepeatedEntries" -> List}], 
     SparseArray[positions -> values, Dimensions[s], 0], 

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


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.