Notes on: Srinivasa, C., Givoni, I., Ravanbakhsh, S., & Frey, B. J. (2017): Min-Max Propagation

Table of Contents

Overview

  • min-max propagation for approximate min-max inference in factor graphs
  • min-max problems that can be efficiently factored into a group of more simple functions

    min_max_propagation_322f98420982123c737219d4800f0276c2286e96.png

Terminology

FG
factor graph
CSP
Constraint Satisfaction Problems
high-order factors
factors min_max_propagation_a96bc78ae7f23093f08f7a23f21d9c0a7366cdb0.png which has "a lot" of variables

Notation

  • min_max_propagation_0207be880056b9a69e22e729dd37bced29cd174a.png variables to minimize over
  • min_max_propagation_0aa0470120f07b61ef9e985225cf9bbd6b79177c.png variables to maximize over
  • min_max_propagation_c4b150a331202915db77a0d2a2ccc73404e42ba6.png is the factorizable min-max problem
  • min_max_propagation_b9e105587b3f7ef9430f31c3e3e5bc63937d7735.png to index the values of min_max_propagation_0aa0470120f07b61ef9e985225cf9bbd6b79177c.png
  • min_max_propagation_fc65b52b481c978fe98c4acae5d87b9900bd2065.png to denote the subset of variables that min_max_propagation_cdd1cc131da6040eca078917132a377727053c44.png depends on when min_max_propagation_79822feb069c0d69a4ceaf3c19961f4f7b42d67e.png
  • min_max_propagation_3a47cd53746ac129a9cc427fed5414867345f6b3.png denotes the variable indices
  • min_max_propagation_486a69441560bc346554e8685f75f564d9151695.png denotes the factor indices
  • min_max_propagation_582f4ef75c4b3550d99554c2766b49ca54ca616c.png denotes the set of neighbouring factor indices for variable min_max_propagation_97eb714dfbd8abb06c6ee1fb2cb049cdaa7defd1.png
  • min_max_propagation_30e440540358ce28de0e1c19e4ce6725452a63d1.png denote the index set of variables connected to factor min_max_propagation_1f36e68578b771d42cf836dbdf0a6923a809fd5c.png
  • Variable-to-Factor messages: The messsage sent from variable min_max_propagation_e9f4d218474bc10aa94958ec30139aee865c0173.png to function min_max_propagation_a96bc78ae7f23093f08f7a23f21d9c0a7366cdb0.png is:

    min_max_propagation_e2e4f410cbc06e5fc9d1bf0973e05e73328be69c.png

    where min_max_propagation_9ca591cff9d84a5faeb2c929926568be0d70d37d.png is the message sent from function min_max_propagation_f0319e6ffaece699f36ce34d21fdd34cefae4824.png to variable min_max_propagation_e9f4d218474bc10aa94958ec30139aee865c0173.png and min_max_propagation_b6e1b8c77a684d08fc060c117fc53373b2911921.png is the set of all neighbouring factors of variable min_max_propagation_97eb714dfbd8abb06c6ee1fb2cb049cdaa7defd1.png, with min_max_propagation_1f36e68578b771d42cf836dbdf0a6923a809fd5c.png removed.

  • Factor-to-Variables Messages: The message sent from function min_max_propagation_a96bc78ae7f23093f08f7a23f21d9c0a7366cdb0.png to variable min_max_propagation_e9f4d218474bc10aa94958ec30139aee865c0173.png is computed using

    min_max_propagation_49d88e843f6843bbd3202ad5226b4a47e4fdb312.png

  • Initialization Using the Identity:

Min-Max Optimization on Factor Graphs

  • Consider min-max problems that can be efficiently factored into a group of more simple functions
  • These min-max problems the following properties:
    1. Cardinality of either min_max_propagation_0207be880056b9a69e22e729dd37bced29cd174a.png or min_max_propagation_0aa0470120f07b61ef9e985225cf9bbd6b79177c.png is linear in available computing resources (e.g. min_max_propagation_0aa0470120f07b61ef9e985225cf9bbd6b79177c.png is an indexing variable min_max_propagation_1f36e68578b771d42cf836dbdf0a6923a809fd5c.png which is linear in the number of indices)
    2. Other variable can be decomposed, so that min_max_propagation_c41f97f6f6b7acd386f17e4fa52ce72577a763cf.png
    3. Given min_max_propagation_0aa0470120f07b61ef9e985225cf9bbd6b79177c.png, the function min_max_propagation_cdd1cc131da6040eca078917132a377727053c44.png depends only on a subset of the variables min_max_propagation_0207be880056b9a69e22e729dd37bced29cd174a.png (a clique) and / or exhibits a form which is easier to minimze individually than when combined with min_max_propagation_43bd1c8770e233d3adad3b5db9ac4b5a60f3a7dc.png
  • Can formulate a factorizable min-max problem as:

    min_max_propagation_a3adc2e75bf8ab36b28d0255f1002bfd88206f71.png

Min-Max Propagation

Initialization using the Identity

In the sum-product algorithm:

  • messages are usually initialized using knowledge of the identity of the product operation.

Consider the case where the FG is a tree with some node chosen as a root, messages can be passed from the leaves to the root and back to the leaves, then:

  • Initial message sent from a variable that is a leaf involves taking the product of an empty set of incoming messages, and therefore the message is initialized to the identity of the group min_max_propagation_4d8205d71a2b01ed14085ae116ed7a32ee11447a.png, which is min_max_propagation_ae4f3750c7a45cd889d509fce10090be1ab21efe.png
  • Need the identity of the min_max_propagation_a9fb42eaee9a55e65f6e6b963f1eea33b18a8381.png semi-group, where

    min_max_propagation_0c258bcd51465f47230e3e5157129dee57e75d99.png

    that is

    min_max_propagation_23e285415fabd2f96befc957331030e68738db41.png

Efficient Update for High-Order Factors

Notation

  • min_max_propagation_3141d6a69f77c26d106a37bfc7f2fe739c525037.png are binary variables
  • min_max_propagation_b9931589ec161d626e1057fa3664035d40578d81.png
  • drop min_max_propagation_1f36e68578b771d42cf836dbdf0a6923a809fd5c.png in factors min_max_propagation_a96bc78ae7f23093f08f7a23f21d9c0a7366cdb0.png and messages min_max_propagation_e783c02019b124e3cdaf97bfb8ca6deefc8bfeeb.png when context is obvious
  • min_max_propagation_52431164d3a649d4db1a1738bb935ca516b4e4a5.png is the largest value min_max_propagation_8700f80c4895c66c1fb785c5b0cf5c4b6f532c75.png that is obtained at some index min_max_propagation_1755a4d5e87b6b399c3545160c059065a3ef73b7.png, for some value min_max_propagation_83c6a6206aa20d6206621a9aea2b1cece0947f81.png:

    min_max_propagation_091fd35280ab6f963c1470dd67915580801edabd.png

    i.e. min_max_propagation_1755a4d5e87b6b399c3545160c059065a3ef73b7.png denotes the index of the min_max_propagation_72360be6610eeb1436b887691a83f89c2263e2b5.png in the above expression, and min_max_propagation_61e7fbc8b4109141121b78f8b006778efdd904ce.png simply denotes if it takes on 0 or 1 value. Further, min_max_propagation_4a8151a8649baf0b3fd1ca7fcd841b9310f49259.png is the index of the next largest message indices up to the min_max_propagation_d80b633218f04f7a25f6a9dd7e4617a38e88f263.png largest ones, and min_max_propagation_2a1fed8e2c7112421374ef383f36a1bd8e112fe6.png be their corresponding assignment

Procedure

Make the following assumptions:

  1. The function min_max_propagation_c877c5335f7a093fb5d523a2110fe92ed8064308.png can be minimized in time min_max_propagation_840458e947eedd4987ded5724266aa53e3b3770f.png with any subset min_max_propagation_0d7b3c7905ba4b9543cf1f2e17138b81c251aca7.png of its variables fixed