# Reparameterization: a Universal Tool for Optimization and Counting

George Katsirelos

<figure><img src="image_1.png" /></figure>

## To cite this version:

George Katsirelos. Reparameterization: a Universal Tool for Optimization and Counting. Beyond NP meeting 2017, May 2017, Paris, France. hal-01604677

HAL Id: hal-01604677

https://hal.science/hal-01604677

Submitted on 5 Jun 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Reparameterization: a Universal Tool for Optimization and Counting

George Katsirelos

10/05/2017

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>
* A set of discrete variables **X**, each with a domain *D*

* We define a joint function on all variables $f : D^X \to S$

* By decomposing the joint function to a set *C* of functions of small arity (*factors*)

* Concise way of describing complicated functions

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>
Function Aggregation – WCSP

$$S \equiv \mathbb{R}^{+} \cup \{0, \infty\}$$

$$f(\mathbf{x}) = \sum_{c \in C} c(\mathbf{x})$$

* f represents a cost or energy or potential

* Each c is a cost function

<figure><img src="image_28.png" /></figure>
Function Aggregation – MRF

$$
S \equiv \mathbb{R}^{+} \cup \{0\}
$$

$$
f(\mathbf{x}) = \prod_{c \in \mathcal{C}} c(\mathbf{x})
$$

• Each c is a probability table

$$
\begin{gather*}
P(\mathbf{x}) = \frac{f(\mathbf{x})}{Z} \\
Z = \frac{1}{\sum_{\mathbf{x}'} \prod_{c \in \mathcal{C}} c(\mathbf{x}')}
\end{gather*}
$$

<figure><img src="image_29.png" /></figure>
* Given MRF $P$, a WCSP $P'$ has

$$c'(\mathbf{x}) = -\log c(\mathbf{x})$$

Then

$$Z = \frac{\exp(-f'(\mathbf{x})) \propto P(\mathbf{x})}{\sum_{\mathbf{x}'} \prod_{c \in C} \exp(-c(\mathbf{x}'))}$$

* So we deal with costs only

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /></figure>

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>

<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>

<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /></figure>

<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>
* Maximum a posteriori estimation

* Compute assignment with maximum probability in MRF

* By equivalence to WCSP, same problem as cost minimization

* Optimization of an NP-hard set, hence $FP^{NP}$

* Generalizes Boolean satisfiability, constraint satisfaction

<figure><img src="image_44.png" /></figure>
Partition Function

* Compute Z, the normalization constant (probability mass of the function)

* $P^{PP}$-complete

* By Toda's theorem, this is Beyond PH

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>

<figure><img src="image_53.png" /></figure>

<figure><img src="image_54.png" /></figure>

<figure><img src="image_55.png" /></figure>

<figure><img src="image_56.png" /></figure>

<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>
Marginal MAP

* Partition **X** into variable sets A, B

* Compute assignment **x**_A that maximizes probability mass of
  $f|_{x_A}$

* NP^PP

<figure><img src="image_59.png" /></figure>
Aside: WCSP as COP

* WCSP combines crisp CSP with arbitrary polynomial objective

* Clever dual bounds

* *Small* arity is not necessary

* Can use the machinery developed in CSP for more expressiveness

* Higher level language

* Propagators

* Global Cost Functions an underexplored area

* New scenarios

* MAP: What's the most likely to succeed schedule

* Marginal MAP: What choices can I make that make schedules more likely to succeed

<figure><img src="image_60.png" /></figure>
Reparameterization

* Use a naive way to compute a bound

* Local transformation that leaves the problem unchanged

* but improves naive bound

* If we touch factors $S$, require

$$ \forall \mathbf{x} \sum_{c \in S} c(\mathbf{x}) = \sum_{c \in S} c'(\mathbf{x}) $$

* Dates back to at least the Held-Karp lower bound for TSP

<figure><img src="image_61.png" /></figure>
WCSP reparameterization

MOVE(c₁, c₂, x, α)

* Shifts α units of cost between c₁ and c₂ on the common assignment x

* Shift direction: sign of α.

* α constrained: no negative costs!

* Commonly restricted to scope(c₁) ⊂ scope(c₂) and in particular |scope(c₁)| = 1:

PROJECT({i}, {i, j}, a, α)

<figure><img src="image_62.png" /></figure>

<figure><img src="image_63.png" /></figure>

<figure><img src="image_64.png" /></figure>

<figure><img src="image_65.png" /></figure>

<figure><img src="image_66.png" /></figure>

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>

<figure><img src="image_69.png" /></figure>

<figure><img src="image_70.png" /></figure>

<figure><img src="image_71.png" /></figure>

<figure><img src="image_72.png" /></figure>

<figure><img src="image_73.png" /></figure>

<figure><img src="image_74.png" /></figure>

<figure><img src="image_75.png" /></figure>

<figure><img src="image_76.png" /></figure>

<figure><img src="image_77.png" /></figure>
Example

<figure><img src="image_78.png" /></figure>

<figure><img src="image_79.png" /></figure>

<figure><img src="image_80.png" /></figure>

<figure><img src="image_81.png" /></figure>

<figure><img src="image_82.png" /></figure>

<figure><img src="image_83.png" /></figure>

<figure><img src="image_84.png" /></figure>

<figure><img src="image_85.png" /></figure>

<figure><img src="image_86.png" /></figure>

<figure><img src="image_87.png" /></figure>

<figure><img src="image_88.png" /></figure>
Example

<figure><img src="image_89.png" /></figure>

<figure><img src="image_90.png" /></figure>
Example

<figure><img src="image_91.png" /></figure>

<figure><img src="image_92.png" /></figure>

<figure><img src="image_93.png" /></figure>

<figure><img src="image_94.png" /></figure>

<figure><img src="image_95.png" /></figure>

<figure><img src="image_96.png" /></figure>

<figure><img src="image_97.png" /></figure>

<figure><img src="image_98.png" /></figure>

<figure><img src="image_99.png" /></figure>

<figure><img src="image_100.png" /></figure>

<figure><img src="image_101.png" /></figure>

<figure><img src="image_102.png" /></figure>

<figure><img src="image_103.png" /></figure>

<figure><img src="image_104.png" /></figure>

<figure><img src="image_105.png" /></figure>

<figure><img src="image_106.png" /></figure>
Example

$$ \mathrm{PROJECT}(\{1, 2\}, \{1\}, b, 1) $$

←

<figure><img src="image_107.png" /></figure>

<figure><img src="image_108.png" /></figure>

<figure><img src="image_109.png" /></figure>

<figure><img src="image_110.png" /></figure>

<figure><img src="image_111.png" /></figure>

<figure><img src="image_112.png" /></figure>

<figure><img src="image_113.png" /></figure>

<figure><img src="image_114.png" /></figure>

<figure><img src="image_115.png" /></figure>

<figure><img src="image_116.png" /></figure>

<figure><img src="image_117.png" /></figure>
Example

$\text{PROJECT}(\{1, 2\}, \{1\}, b, 1)$

<figure><img src="image_118.png" /></figure>

$\rightarrow \quad \text{PROJECT}(\{1, 2\}, \{1\}, b, -1)$

<figure><img src="image_119.png" /></figure>
Example

$\mathrm{PROJECT}(\{1, 2\}, \{1\}, b, 1)$

<figure><img src="image_120.png" /></figure>

↓ $\mathrm{PROJECT}()\{1\}, \emptyset, []$, $1)$

<figure><img src="image_121.png" /></figure>
Example

$\mathrm{PROJECT}(\{1, 2\}, \{1\}, b, 1)$

←

<figure><img src="image_122.png" /></figure>

<figure><img src="image_123.png" /></figure>

↓

$\mathrm{PROJECT}()\{(1\}, \emptyset, \emptyset, 1)$

$c_{\emptyset} = 1$

<figure><img src="image_124.png" /></figure>
Lower bounds for cost minimization

* The sum of the lower bound of each function $\min_x \sum_c c(x) \le \sum_c \min_{x \in c} c(x)$

<figure><img src="image_125.png" /></figure>

<figure><img src="image_126.png" /></figure>

<figure><img src="image_127.png" /></figure>

<figure><img src="image_128.png" /></figure>

<figure><img src="image_129.png" /></figure>

<figure><img src="image_130.png" /></figure>

<figure><img src="image_131.png" /></figure>

<figure><img src="image_132.png" /></figure>

<figure><img src="image_133.png" /></figure>

<figure><img src="image_134.png" /></figure>

<figure><img src="image_135.png" /></figure>

<figure><img src="image_136.png" /></figure>

<figure><img src="image_137.png" /></figure>

<figure><img src="image_138.png" /></figure>

<figure><img src="image_139.png" /></figure>
Min Sum Diffusion

① Choose overlapping factors $c_1, c_2$

② For every x in the intersection, choose α so that $c_1(x) = c_2(x)$

③ Repeat until convergence

• Averages factors

• Will converge as number of iterations goes to infinity, as long as each pair of factors is chosen infinitely often

• Will converge to arc consistent state

<figure><img src="image_140.png" /></figure>

<figure><img src="image_141.png" /></figure>

<figure><img src="image_142.png" /></figure>

<figure><img src="image_143.png" /></figure>

<figure><img src="image_144.png" /></figure>

<figure><img src="image_145.png" /></figure>

<figure><img src="image_146.png" /></figure>

<figure><img src="image_147.png" /></figure>

<figure><img src="image_148.png" /></figure>

<figure><img src="image_149.png" /></figure>

<figure><img src="image_150.png" /></figure>

<figure><img src="image_151.png" /></figure>

<figure><img src="image_152.png" /></figure>

<figure><img src="image_153.png" /></figure>

<figure><img src="image_154.png" /></figure>
Block Coordinate Descent

* Min Sum Diffusion is a Block Coordinate Descent algorithm

* Differentiate on subproblem, order of updates

* At best will converge to optimum of linear relaxation

* Perform pruning

<figure><img src="image_155.png" /></figure>

<figure><img src="image_156.png" /></figure>

<figure><img src="image_157.png" /></figure>

<figure><img src="image_158.png" /></figure>

<figure><img src="image_159.png" /></figure>

<figure><img src="image_160.png" /></figure>

<figure><img src="image_161.png" /></figure>

<figure><img src="image_162.png" /></figure>

<figure><img src="image_163.png" /></figure>

<figure><img src="image_164.png" /></figure>

<figure><img src="image_165.png" /></figure>
Branch-and-bound

1. Start with root node, corresponding to initial problem

2. Pick an *open* node

3. Compute dual bound

1. If the primal bound is violated, *close* node; else

2. Make a binary choice, replace by two new nodes

4. Go to step 2

<figure><img src="image_166.png" /></figure>

<figure><img src="image_167.png" /></figure>

<figure><img src="image_168.png" /></figure>

<figure><img src="image_169.png" /></figure>

<figure><img src="image_170.png" /></figure>

<figure><img src="image_171.png" /></figure>

<figure><img src="image_172.png" /></figure>

<figure><img src="image_173.png" /></figure>

<figure><img src="image_174.png" /></figure>

<figure><img src="image_175.png" /></figure>

<figure><img src="image_176.png" /></figure>

<figure><img src="image_177.png" /></figure>
Upper bound for Partition Function

* Product of mass of all factors

$$Z = \sum_{\mathbf{x}} \prod_{c} \exp(-c(\mathbf{x})) \le \prod_{c} \sum_{\mathbf{x}} \exp(-c(\mathbf{x}))$$

* Proof: by distributing the product over the sum

<figure><img src="image_178.png" /></figure>
Approximate Z

* Branch and bound

* Ignore subtrees as long as the contribution is small enough

1. Start with root node, corresponding to initial problem, $U = 0$

2. Pick an *open* node

3. Compute Z upper bound $u$

1. If $u < \varepsilon U$, close node; else

2. If full assignment, add its weight to $U$; else

3. Make a binary choice, replace by two new nodes

4. Go to step 2

<figure><img src="image_179.png" /></figure>

<figure><img src="image_180.png" /></figure>

<figure><img src="image_181.png" /></figure>

<figure><img src="image_182.png" /></figure>

<figure><img src="image_183.png" /></figure>

<figure><img src="image_184.png" /></figure>

<figure><img src="image_185.png" /></figure>

<figure><img src="image_186.png" /></figure>

<figure><img src="image_187.png" /></figure>

<figure><img src="image_188.png" /></figure>

<figure><img src="image_189.png" /></figure>

<figure><img src="image_190.png" /></figure>

<figure><img src="image_191.png" /></figure>

<figure><img src="image_192.png" /></figure>

<figure><img src="image_193.png" /></figure>

<figure><img src="image_194.png" /></figure>
Marginal MAP

* Prune subtree as soon as upper bound for $Z(f_{x_A})$ is lower than incumbent

① Start with root node, corresponding to initial problem

② Pick an *open* node

③ Compute $Z(f|_{x_A})$ upper bound $u$

① If $u < \varepsilon U$, *close* node; else

② If all $A$ variables have been assigned, compute $Z(f_{x_A})$, replacing incumbent if needed; else

③ Make a binary choice on variables in $A$, replace by two new nodes

④ Go to step 2

<figure><img src="image_195.png" /></figure>
Conclusions

* Reparameterization is a universal tool

* Maintains cost/probability of all assignments, so always applicable

* Non-trivial improvement of trivial bounds

* Precise connection to linear programming in cost minimization

* Hierarchies of strengthening reparameterizations which change network

* Linear programming cuts

<figure><img src="image_196.png" /></figure>

<figure><img src="image_197.png" /></figure>

<figure><img src="image_198.png" /></figure>

<figure><img src="image_199.png" /></figure>

<figure><img src="image_200.png" /></figure>

<figure><img src="image_201.png" /></figure>

<figure><img src="image_202.png" /></figure>

<figure><img src="image_203.png" /></figure>

<figure><img src="image_204.png" /></figure>

<figure><img src="image_205.png" /></figure>

<figure><img src="image_206.png" /></figure>
Q?

<figure><img src="image_207.png" /></figure>

<figure><img src="image_208.png" /></figure>

<figure><img src="image_209.png" /></figure>

<figure><img src="image_210.png" /></figure>

<figure><img src="image_211.png" /></figure>

<figure><img src="image_212.png" /></figure>

<figure><img src="image_213.png" /></figure>

<figure><img src="image_214.png" /></figure>

<figure><img src="image_215.png" /></figure>

<figure><img src="image_216.png" /></figure>

<figure><img src="image_217.png" /></figure>