none
Defining potential functions (Migrated from community.research.microsoft.com)

    Question

  • amchiclet posted on 02-11-2010 4:38 PM

    I need some help defining potential functions in a Markov Network.

    Suppose I have 2 nodes, x1 and x2 connected together.

    Let each random variable have 2 possible values, 0 and 1.

    Here's phi's definition.

    phi(x1=0) = 1
    phi(x1=1) = 2
    phi(x2=0) = 3
    phi(x2=1) = 4 

    And here's psi's definition.

    psi(x1=0, x2=0) = 5
    psi(x1=0, x2=1) = 6
    psi(x1=1, x2=0) = 7
    psi(x1=1, x2=1) = 8

    How would we model this in Infer.NET?

    Thank you.

    Friday, June 03, 2011 6:04 PM

Answers

  • minka replied on 09-30-2010 6:56 AM

    Thanks for pointing this out.  It turns out this is a bug in version 2.3.  It will be fixed in the next version.  Meanwhile, you can work around by adding the following weird bit of code to your model:

                                  for (int i = 0; i < 10; i++) {

                                        Variable.ConstrainEqualRandom(x, Discrete.Uniform(2));

                                        Variable.ConstrainEqualRandom(y, Discrete.Uniform(2));

                                        Variable.ConstrainEqualRandom(z, Discrete.Uniform(2));

                                  }

    This doesn't change the model mathematically but it causes Infer.NET to choose a better update schedule for this type of model.  Specifically, it encourages Infer.NET to send messages from the priors down to the constraints, rather than the other way around which causes the problem.  If you intend to build a larger model of this type, just be sure to add these dummy constraints for every variable.

    Friday, June 03, 2011 6:05 PM

All replies

  • minka replied on 02-15-2010 11:00 AM

    The most efficient way to represent such models is by writing the unary potentials as Bernoulli priors, and writing the pairwise potentials as soft equality constraints.  Note that any strictly positive pairwise potential on binary variables can be written as a soft equality potential times some extra unary potentials.  Here is some example code for this model that uses this technique.  I've provided a helper function called BinaryPairwiseAsEquality that makes it easy to convert any binary pairwise potential into a soft equality.  Examining the value of equalityLogOdds shows that it is negative, i.e. the pairwise potential you provided actually prefers x1 and x2 to be unequal.

                /// <summary>

                /// Inference on an undirected graph with binary unary and pairwise potentials.

                /// </summary>

                /// <remarks>

                /// Note that the generated model involves only 3 constants, instead of the 8 constants required by the tabular representation.

                /// </remarks>

                public void BinaryPairwisePotentials()

                {

                      double x1LogOdds = Math.Log(2.0/1.0); // first unary potential

                      double x2LogOdds = Math.Log(4.0/3.0); // second unary potential

                      double equalityLogOdds, aLogOdds, bLogOdds;

                      BinaryPairwiseAsEquality(5, 6, 7, 8, out equalityLogOdds, out aLogOdds, out bLogOdds);

     

                      Variable<bool> x1 = Variable.BernoulliFromLogOdds(x1LogOdds+aLogOdds);  // combine the unary potentials into one prior distribution

                      Variable<bool> x2 = Variable.BernoulliFromLogOdds(x2LogOdds+bLogOdds);

                      Variable.ConstrainEqualRandom(x1==x2, Bernoulli.FromLogOdds(equalityLogOdds)); // represent the pairwise potential as soft equality

     

                      InferenceEngine engine = new InferenceEngine();

                      Console.WriteLine("x1 = {0}", engine.Infer(x1)); // x1 = Bernoulli(0.731)

                      Console.WriteLine("x2 = {0}", engine.Infer(x2)); // x2 = Bernoulli(0.6069)

                }

     

                /// <summary>

                /// Represent a binary pairwise factor as a soft equality times unary potentials.

                /// </summary>

                /// <param name="pFF">Potential value for FF case</param>

                /// <param name="pFT">Potential value for FT case</param>

                /// <param name="pTF">Potential value for TF case</param>

                /// <param name="pTT">Potential value for TT case</param>

                /// <param name="equalityLogOdds">LogOdds of the soft equality</param>

                /// <param name="aLogOdds">LogOdds of first variable's unary potential</param>

                /// <param name="bLogOdds">LogOdds of second variable's unary potential</param>

                public static void BinaryPairwiseAsEquality(double pFF, double pFT, double pTF, double pTT, out double equalityLogOdds, out double aLogOdds, out double bLogOdds)

                {

                      double logFF = Math.Log(pFF);

                      double logFT = Math.Log(pFT);

                      double logTF = Math.Log(pTF);

                      double logTT = Math.Log(pTT);

                      equalityLogOdds = 0.5*(logFF+logTT-logFT-logTF);

                      aLogOdds = equalityLogOdds + logTF - logFF;

                      bLogOdds = equalityLogOdds + logFT - logFF;

                }

     

     

    Friday, June 03, 2011 6:04 PM
  • amchiclet replied on 02-15-2010 12:25 PM

    Minka, thank you so much. I have to take my time understanding how this works.

    Since you said this is the most efficient way, my guess is that it includes some math and knowledge of the potential functions (e.g. strictly positive on binary variables). Will a more generic but less efficient model be more complicated than this?

    At the end, the challenge of learning Infer.NET is mostly about representing the most efficient model to express the problem right?

    Thanks.

    Friday, June 03, 2011 6:04 PM
  • amchiclet replied on 02-15-2010 3:39 PM

    And as a concrete example what I'm asking, what if each variable had 3 possible values {1,2,3}? Would the log odds approach still work? Thanks.

    Friday, June 03, 2011 6:04 PM
  • minka replied on 02-16-2010 6:22 AM

    The transformation I described is only for boolean variables.

    Friday, June 03, 2011 6:04 PM
  • amchiclet replied on 03-02-2010 6:23 PM

    Hi,

    I tried to convert your code above to use discrete variables instead.

    I also re-factored the functions to look like this -- u for unary and b for binary.

                P(X) = u1(x1) u2(x2) bFF(x1,x2) bFT(x1,x2) bTF(x1,x2) bTT(x1,x2)

    where

                u1(x1==0) = 1/3
                u1(x1==1) = 2/3

                u2(x2==0) = 3/7
                u2(x2==1) = 4/7

                bFF(x1==0,x2==0) = 5
                bFF(else) = 1

                bFT(x1==0,x2==1) = 6
                bFT(else) = 1

                bTF(x1==1,x2==0) = 7
                bTF(else) = 1

                bTT(x1==1,x2==1) = 8
                bTT(else) = 1 

    I did the calculation on paper and the numbers were right (or that's what I thought).

    And here's my code.

                double[] x1Probs = { 1.0 / 3.0, 2.0 / 3.0 };
                Variable<int> x1 = Variable.Discrete(x1Probs);
                double[] x2Probs = { 3.0 / 7.0, 4.0 / 7.0 };
                Variable<int> x2 = Variable.Discrete(x2Probs);

                Variable<bool> f1 = (x1 == 0);
                Variable<bool> t1 = (x1 == 1);
                Variable<bool> f2 = (x2 == 0);
                Variable<bool> t2 = (x2 == 1);

                Variable<bool> ff = (f1 & f2);
                Variable<bool> ft = (f1 & t2);
                Variable<bool> tf = (t1 & f2);
                Variable<bool> tt = (t1 & t2);

                Variable.ConstrainEqualRandom(ff, Bernoulli.FromLogOdds(Math.Log(5.0/1.0)));
                Variable.ConstrainEqualRandom(ft, Bernoulli.FromLogOdds(Math.Log(6.0/1.0)));
                Variable.ConstrainEqualRandom(tf, Bernoulli.FromLogOdds(Math.Log(7.0/1.0)));
                Variable.ConstrainEqualRandom(tt, Bernoulli.FromLogOdds(Math.Log(8.0/1.0)));

    When I inferred x1 and x2, I got the following.

    x1 = Discrete(0.3696 0.6304)
    x2 = Discrete(0.4399 0.5601)

    which aren't the correct numbers.

    Does anybody know what I did wrong? Thanks for the help.

    Friday, June 03, 2011 6:04 PM
  • amchiclet replied on 03-02-2010 9:34 PM

    I just figured out. I was confused and thought that the potential functions I was defining could be expressed via ContrainEqualRandom, which was not the case.

    Friday, June 03, 2011 6:04 PM
  • minka replied on 09-24-2010 8:54 AM

    Actually the model you've written is correct.  The answer is different due to the approximate inference, in this case belief propagation.  Belief propagation operates on a factor graph.  Each constraint that you specify in the program becomes a separate factor, joining the two variables x1 and x2 in the graph.  When there are two or more such factors, the factor graph has a loop and the results become inexact.  This is why it is important to use the minimal number of factors to express a model.  (You can verify that the model is correct by using GibbsSampling for inference.  With enough samples, it can get arbitrarily close to the correct answer.)

    Friday, June 03, 2011 6:05 PM
  • smh0816 replied on 09-27-2010 10:39 AM

    Thanks, Minka.

    I have understood how you model using only one constraint that makes a factor graph with one factor.

    However, your code models a simple case which have only two labels (true/false).

    I wonder if one can model multi-label pairwise MRF using only one factor(constraint) for each pair.

    I have also seen the case which has multiple labels from the link below:

    http://community.research.microsoft.com/forums/t/4542.aspx

    But this way requires multiple factors for each pair.

    Friday, June 03, 2011 6:05 PM
  • minka replied on 09-27-2010 12:02 PM

    You can do this by defining a new variable which ranges over all combinations of the pair, then giving it a prior that matches the desired potential.  For example,

                            Variable<int> x1x2 = Variable.Discrete(5, 6, 7, 8);

                            using (Variable.Case(x1x2, 0)) {

                                  Variable.ConstrainEqual(x1, 0);

                                  Variable.ConstrainEqual(x2, 0);

                            }

                            using (Variable.Case(x1x2, 1)) {

                                  Variable.ConstrainEqual(x1, 0);

                                  Variable.ConstrainEqual(x2, 1);

                            }

                            using (Variable.Case(x1x2, 2)) {

                                  Variable.ConstrainEqual(x1, 1);

                                  Variable.ConstrainEqual(x2, 0);

                            }

                            using (Variable.Case(x1x2, 3)) {

                                  Variable.ConstrainEqual(x1, 1);

                                  Variable.ConstrainEqual(x2, 1);

                            }

     

     

    This gives the correct answer for the problem above using belief propagation.  This approach generalizes to any number of labels and any number of variables participating in the factor.  You can also learn the potential values (5,6,7,8), for example by getting them from a Dirichlet-distributed vector.

    Friday, June 03, 2011 6:05 PM
  • smh0816 replied on 09-29-2010 8:02 AM

    Using your code, I made a simple model.

    But it does not work and give me an error: (System.DivideByZeroException)

    I have no idea what happens in inferring system...

     

     

    int length = 2;

     

                double[] xProbs = { 0.4, 0.6 };

                Variable<int> x = Variable.Discrete(xProbs).Named("x");

                double[] yProbs = { 0.7, 0.3 };

                Variable<int> y = Variable.Discrete(yProbs).Named("y");

                double[] zProbs = { 0.8, 0.2 };

                Variable<int> z = Variable.Discrete(zProbs).Named("z");

     

                Variable<int> xy = Variable.Discrete(1.0, 0.5, 0.5, 1.0);

                Variable<int> yz = Variable.Discrete(1.0, 0.5, 0.5, 1.0);

                Variable<int> zx = Variable.Discrete(1.0, 0.5, 0.5, 1.0);

     

                int pair_index = 0;

     

                for (int i = 0; i < length; i++)

                {

                    for (int j = 0; j < length; j++, pair_index++)

                    {

                        using (Variable.Case(xy, pair_index))

                        {

                            Variable.ConstrainEqual(x, i);

                            Variable.ConstrainEqual(y, j);

                        }

     

                        using (Variable.Case(yz, pair_index))

                        {

                            Variable.ConstrainEqual(y, i);

                            Variable.ConstrainEqual(z, j);

                        }

     

                        using (Variable.Case(zx, pair_index))

                        {

                            Variable.ConstrainEqual(z, i);

                            Variable.ConstrainEqual(x, j);

                        }

                    }

                }

     

                InferenceEngine engine = new InferenceEngine(new ExpectationPropagation());

     

                // Retrieve the posterior distributions

                Console.WriteLine("x = " + engine.Infer(x));

                Console.WriteLine("y = " + engine.Infer(y));

                Console.WriteLine("z = " + engine.Infer(z));

     

     

    Friday, June 03, 2011 6:05 PM
  • minka replied on 09-30-2010 6:56 AM

    Thanks for pointing this out.  It turns out this is a bug in version 2.3.  It will be fixed in the next version.  Meanwhile, you can work around by adding the following weird bit of code to your model:

                                  for (int i = 0; i < 10; i++) {

                                        Variable.ConstrainEqualRandom(x, Discrete.Uniform(2));

                                        Variable.ConstrainEqualRandom(y, Discrete.Uniform(2));

                                        Variable.ConstrainEqualRandom(z, Discrete.Uniform(2));

                                  }

    This doesn't change the model mathematically but it causes Infer.NET to choose a better update schedule for this type of model.  Specifically, it encourages Infer.NET to send messages from the priors down to the constraints, rather than the other way around which causes the problem.  If you intend to build a larger model of this type, just be sure to add these dummy constraints for every variable.

    Friday, June 03, 2011 6:05 PM