Worst-case Optimal Submodular Extensions for Marginal Estimation

arXiv:1801.06490v1 [cs.LG] 10 Jan 2018

Pankaj Pansari1,2
1: University of Oxford
pankaj@robots.ox.ac.uk

Chris Russell 2,3
2: The Alan Turing Institute
crussell@turing.ac.uk

Abstract
Submodular extensions of an energy function
can be used to efficiently compute approximate marginals via variational inference. The
accuracy of the marginals depends crucially on
the quality of the submodular extension. To
identify the best possible extension, we show
an equivalence between the submodular extensions of the energy and the objective functions
of linear programming (LP) relaxations for
the corresponding MAP estimation problem.
This allows us to (i) establish the worst-case
optimality of the submodular extension for
Potts model used in the literature; (ii) identify
the worst-case optimal submodular extension
for the more general class of metric labeling;
and (iii) efficiently compute the marginals for
the widely used dense CRF model with the
help of a recently proposed Gaussian filtering
method. Using synthetic and real data, we
show that our approach provides comparable
upper bounds on the log-partition function to
those obtained using tree-reweighted message
passing (TRW) in cases where the latter is
computationally feasible. Importantly, unlike
TRW, our approach provides the first practical algorithm to compute an upper bound on
the dense CRF model.

1

Introduction

The desirable optimization properties of submodular
set functions have been widely exploited in the design
of approximate MAP estimation algorithms for discrete
conditional random fields (CRFs) [Boykov et al., 2001;
Kumar et al., 2011]. Submodularity has also been
recently used to design an elegant variational inference
algorithm to compute the marginals of a discrete CRF

Accepted at AISTATS 2018.

M. Pawan Kumar1,2
3: University of Surrey
pawan@robots.ox.ac.uk

by minimising an upper-bound on the log-partition
function. In the initial work of [Djolonga and Krause,
2014], the energy of the CRF was restricted to be
submodular. In a later work [Zhang et al., 2015], the
algorithm was extended to handle more general Potts
energy functions. The key idea here is to define a
large ground set such that its subsets represent valid
labelings, sublabelings or even incorrect labelings (these
may assign two separate labels to a random variable
and hence be invalid). Given the large ground set, it
is possible to define a submodular set function whose
value is equal to the energy of the CRF for subsets that
specify a valid labeling of the model. We refer to such
a set function as a submodular extension of the energy.
For a given energy function, there exists a large number
of possible submodular extensions. The accuracy of the
variational inference algorithm depends crucially on
the choice of the submodular extension. Yet, previous
work has largely ignored the question of identifying
the best extension. Indeed, the difficulty of identifying submodular extensions of general energy functions
could be a major reason why the experiments of [Zhang
et al., 2015] were restricted to the special case of models
specified by the Potts energy functions.
In this work, we establish a hitherto unknown connection between the submodular extension of the Potts
model proposed by Zhang et al. [2015], and the objective function of an accurate linear programming (LP)
relaxation of the corresponding MAP estimation problem [Kleinberg and Tardos, 2002]. This connection
has three important practical consequences. First, it
establishes the accuracy of the submodular extension
of the Potts model, via the UGC-hardness worst-case
optimality of the LP relaxation. Second, it provides
an accurate submodular extension of the hierarchical
Potts model, via the LP relaxation of the corresponding MAP estimation problem proposed by Kleinberg
and Tardos [2002]. Since any metric can be accurately
approximated as a mixture of hierarchical Potts models [Bartal, 1996, 1998], this result also provides a
computationally feasible algorithm for estimating the
marginals for metric labeling. Third, it establishes the

Worst-case Optimal Submodular Extensions for Marginal Estimation

equivalence between the subgradient of the LP relaxation and the conditional gradient of the problem of
minimising the upper bound of the log-partition. This
allows us to employ the widely used dense CRF, since
the subgradient of its LP relaxation can be efficiently
computed using a recently proposed modified Gaussian filtering algorithm [Ajanthan et al., 2017]. As a
consequence, we provide the first efficient algorithm to
compute an upper bound of the log-partition function
of dense CRFs. This provides complementary information to the popular mean-field inference algorithm
for dense CRFs, which computes a lower bound on
the log-partition [Koltun and Krahenbuhl, 2011]. We
show that the quality of our solution is comparable to
tree reweighted message passing (TRW) [Wainwright
et al., 2005] for the case of sparse CRFs. Unlike our
approach, TRW is computationally infeasible for dense
CRFs, thereby limiting its use in practice. Using dense
CRF models, we perform stereo matching on standard
data sets and obtain better results than [Koltun and
Krahenbuhl, 2011]. The complete code is available at
https://github.com/pankajpansari/denseCRF.

2

Preliminaries

We now introduce the notation and definitions that we
will make use of in the remainder of the paper.
Submodular Functions Given a ground set U =
{1, . . . , N }, denote by 2U its power set. A set function
F : 2U → R is submodular if, for all subsets A, B ⊆ U ,
we have
F (A ∪ B) + F (A ∩ B) ≤ F (A) + F (B).

(1)

The set function FPis modular if there exists s ∈ RN
such that F (A) = k∈A sk ∀ A ⊆ 2U . P
Henceforth, we
will use the shorthand s(A) to denote k∈A sk .
Extended Polymatroid Associated with any submodular function F is a special polytope known as the
extended polymatroid defined as
EP (F ) = {s ∈ RN | ∀A ⊆ U : s(A) ≤ F (A)},

(2)

where s denotes the modular function s(.) considered
as a vector.
Lovasz Extension For a given set function F with
F (∅) = 0, the value of its Lovasz extension f (w) :
RN → R is defined as follows: order the components of
w in decreasing order such that wj1 ≥ wj2 ≥ · · · ≥ wjN ,
where (j1 , j2 , . . . , jN ) is the corresponding permutation
of the indices. Then,
f (w) =

N
X

The function f is an extension because it equals F on
the vertices of the unit cube. That is, for any A ⊆ V ,
f (1A ) = F (A) where 1A is the 0-1 indicator vector
corresponding to the elements of A.
Property 1. By Edmond’s greedy algorithm [Edmonds, 1970], if w ≥ 0 (non-negative elements),
f (w) =

wjk (F (j1 , . . . , jk ) − F (j1 , . . . , jk−1 )) .
(3)

(4)

Property 1 implies that an LP over EP (F ) can be
solved by computing the value of the Lovasz extension
using equation (3).
Property 2. The Lovasz extension f of a submodular
function F is a convex piecewise linear function.
Property 2 holds since f (w) is the pointwise maximum
of linear functions according to equation (4).
CRF and Energy Functions A CRF is defined as a
graph on a set of random variables X = {X1 , . . . , XN }
related by a set of edges N . We wish to assign
every variable Xa one of the labels from the set
L = {1, 2, . . . , L}. The quality of a labeling x is given
by an energy function defined as
X
X
E(x) =
φa (xa ) +
φab (xa , xb ),
(5)
a∈X

(a,b)∈N

where φa and φab are the unary and pairwise potentials
respectively. In computer vision, we often think of X as
arranged on a grid. A sparse CRF has N defined by 4connected or 8-connected neighbourhood relationships.
In a dense CRF, on the other hand, every variable is
connected to every other variable.
The energy function also defines a probability distribution P (x) as follows:
(
1
exp(−E(x))
if x ∈ LN ,
P (x) = Z
(6)
0
otherwise.
P
The normalization factor Z = x∈LN exp(−E(x)) is
known as the partition function.
Inference There are two types of inference problems
in CRFs:
(i) Marginal inference: We want to compute the
marginal probabilities P (Xa = i) for every a =
1, 2, . . . , N and i = 1, 2, . . . , L.
(ii) MAP inference: We want to find a labeling with the
minimum energy, that is, minx∈LN E(x). Equivalently,
MAP inference finds the mode of P (x).

3

k=1

max hw, si.
s∈EP (F )

Review: Variational Inference Using
Submodular Extensions

We now summarise the marginal inference method of
Zhang et al. [2015]. To do this, we need to first define

Pankaj Pansari1,2 , Chris Russell

2,3

, M. Pawan Kumar1,2

problem as
s∈EP (F )

Figure 1: Illustration of 1-of-L encoding used in [Zhang
et al., 2015] with 4 variables and 3 labels. The blue labeling,
corresponding to X1 = 1, X2 = 3, X3 = 2, X4 = 1, is
valid. The yellow labeling, corresponding to X2 = 2, X3 =
1, 3, X4 = 3, is invalid since X3 has been assigned multiple
labels and X1 has been assigned none.
submodular extensions.
Submodular Extensions A submodular extension
is defined using a ground set such that some of its
subsets correspond to valid CRF labelings. To such an
extension, we need an encoding scheme which gives the
sets corresponding to valid CRF labelings.
One example of an encoding scheme is the 1-of-L encoding, illustrated in figure 1. Let each variable Xa
take one of L possible labels. In this scheme, we represent the set of possible assignments for Xa by the
set Va = {va1 , va2 , . . . , vaL }. If Xa is assigned label i,
then we select the element vai . Extending to all variables, our ground set becomes V = ∪N
a=1 Va . A valid
assignment A ⊆ V assigns each variable exactly one
label, that is, |A ∩ Va | = 1 for all Va . We denote the
set of valid assignments by M where M = ∩N
a=1 Ma
and Ma = {A : |A ∩ Va | = 1}.
Using our ground set V , we can define a submodular
function F which equals E(x) for all sets corresponding
to valid labelings, that is, F (Ax ) = E(x), x ∈ LN
where Ax is the set encoding of x. We call such a
function F a submodular extension of E(x).
Upper-Bound on Log-Partition Using a submodular extension F and given any s ∈ EP (F ), we can
obtain an upper-bound on the partition function as
Z=

X
A∈M

exp(−F (A)) ≤

X

exp(−s(A)),

(7)

A∈M

where M is the set of valid labelings. The upperbound is the partition function of the distribution
Q(A) ∝ exp(−s(A)), which factorises fully because
s(.) is modular. Since s ∈ EP (F ) is a free parameter,
we can obtain good approximate marginals of the distribution P (·) by minimising the upper-bound. After
taking logs, we can equivalently write our optimisation

X

g(s), where g(s) = log

min

exp(−s(A)). (8)

A∈M

Conditional Gradient Algorithm The conditional gradient algorithm (algorithm 1) [Frank and
Wolfe, 1956] is a good candidate for solving problem
(8) due to two reasons. First, problem (8) is convex.
Second, as solving an LP over EP(F) is computationally
tractable (property 1), the conditional gradient can be
found efficiently. The algorithm starts with an initial
solution s0 (line 1). At each iteration, we compute the
conditional gradient s∗ (line 3), which minimises the
linear approximation g(sk ) + ∇g(sk )T (s − sk ) of the objective function. Finally, s is updated by either (i) fixed
step size schedule, as in line 7 of algorithm 1, or (ii) by
doing line search sk+1 = min0≤γ≤1 g(γs∗ + (1 − γ)sk ).
Algorithm 1 Upper Bound Minimisation using Conditional Gradient Descent
1: Initialize s = s0 ∈ EP (F )
2: for k = 1 to MAX_ITER do
3:
s∗ = argmins∈EP (F ) h∇g(sk ), si
4:
if hs∗ − sk , ∇g(sk )i ≤  then
5:
break
6:
end if
7:
sk+1 = sk + γ(s∗ − sk ) with γ = 2/(k + 2)
8: end for
9: return s

4

Worst-case Optimal Submodular
Extensions via LP Relaxations

Worst-case Optimal Submodular Extensions
Different choices of extensions F change the domain in
problem (8), leading to different upper bounds on the
log-partition function. How does one come up with an
extension which yields the tightest bound?
In this paper, we focus on submodular extension families F(.) which for each instance of the energy function
E(.) belonging to a given class E gives a corresponding
submodular extension F(E). We find the extension
family Fopt that is worst-case optimal. This implies
that there does not exist another submodular extension
family F that gives a tighter upper bound for problem
(8) than Fopt for all instances of the energy function in
E. Formally,
@F :

min
s∈EP (F (E))

g(s) ≤

min

g(s) ∀ E(.) ∈ E.

s∈EP (Fopt (E))

(9)
Note that our problem is different from taking a given
energy model and obtaining a submodular extension
which is optimal for that model. Also, we seek a closedform analytical expression for F. For the sake of clarity,

Worst-case Optimal Submodular Extensions for Marginal Estimation

Tightest LP Relaxation Before describing our set
encoding and submodular extension, we briefly outline
the LP relaxation of the corresponding MAP estimation
problem. To this end, we define indicator variables yai
which equal 1 if Xa = i, and 0 otherwise. The following
LP relaxation is the tightest known for Potts model in
the worst-case, assuming the Unique Games Conjecture
to be true [Manokaran et al., 2008]
XX
(P-LP) min E(y) =
φa (i)yai +
y

a

i

X X wab
· |yai − ybi |
2
i

(a,b)∈N

s.t y ∈ ∆.
Figure 2: An illustration of the worst-case optimal submodular extension for Potts model for a chain graph of
4 variables, each of which can take 3 labels. The figure
shows the way to compute the extension values of the set
A = {v1,1 , v4,1 , v3,2 }.
in the analysis that follows we use F to represent F(E)
where the meaning is clear from context. The two
classes of energy functions we consider in this paper
are Potts and hierarchical Potts families.
Using LP Relaxations If we introduce a temperature parameter in P (x) (equation (6)) by using E(x)/T
and decrease T , the resulting distribution starts to
peak more sharply around its mode. As T → 0,
marginal estimation becomes the same as MAP inference since the resulting distribution P 0 (x) has mass
1 at its mode x∗ and is 0 everywhere else. Given the
MAP solution x∗ , one can compute the marginals as
P (Xi = j) = [x∗i = j], where [.] is the Iverson bracket.

(11)

The set ∆ is the union of N probability simplices:
∆ = {ya ∈ RL |ya ≥ 0 and h1, ya i = 1},

(12)

where y is the vector of all variables and ya is the
component of y corresponding to Xa .
Set Encoding We choose to use the 1-of-L encoding
for Potts model as described in section 3. With the
encoding scheme for Potts model above, g(s) can be
factorised and problem (8) can be rewritten as:

min
s∈EP (F )

N
X

log

a=1

L
X

exp(−sai ).

(13)

i=1

(See Remark 1 in appendix)
Marginal Estimation with Temperature We
now introduce a temperature parameter T > 0 to
problem (13) which divides E(x), or equivalently divides s belonging to EP (F ). Also, since T > 0, we
can multiply the objective by T leaving the problem
unchanged. Without changing the solution, we can
transform problem (13) as follows

Motivated by this connection, we ask if one can introduce a temperature parameter to our problem (8) and
transform it to an LP relaxation in the limit T → 0?
We can then hope to use the tightest LP relaxations
of MAP problems known in literature to find worstcase optimal submodular extensions. We answer this
question in affirmative. Specifically, in the following
two sections we show how one can select the set encoding and submodular extension to convert problem
(8) to the tightest known LP relaxations for Potts and
hierarchical Potts models. Importantly, we prove the
worst-case optimality of the extensions thus obtained.

Worst-case Optimal Submodular Extension
We now connect our marginal estimation problem (8)
with LP relaxations using the following proposition.

5

Proposition 1. Using the 1-of-L encoding scheme, in
the limit T → 0, problem (34) for Potts model becomes:

Potts Model

The Potts model, also known as the uniform metric,
specifies the pairwise potentials φab (xa , xb ) in equation
(5) as follows:
φab (xa , xb ) = wab · [xa 6= xb ],

min
s∈EP (F )

gT (s) =

N
X

T · log

a=1

L
X
i=1

exp(−

sai
).
T

− min f (y)
y∈∆

(14)

(15)

where f (.) is the Lovasz extension of F (.).
(Proof in appendix)

(10)

where wab is the weight associated with edge (a, b).

The above problem is equivalent to an LP relaxation
of the corresponding MAP estimtation problem (see

Pankaj Pansari1,2 , Chris Russell

2,3

, M. Pawan Kumar1,2

s

1-1

1-2

1-3

2-1

φ (3)
φ1(1) φ1(2) 1

2-2

2-3

φ2(1) φ2(2)
φ2(3)

t

Figure 3: An st-graph specifying the worst-case optimal
submodular extension for Potts model for 2 variables with 3
labels each and connected to each other. There is a node for
each variable and each label, that is, for all elements of the
ground set. The nodes have been labeled as ‘variable-label’,
hence node 1-1 represents the element v11 and so on. The
solid blue arcs model the unary potentials, and the dotted
red arcs represent the pairwise potentials. Each dotted red
arc has weight w12 /2.
Remark 2 in appendix). We note that gT (s) in problem
(34) becomes the objective function of an LP relaxation
in the limit T → 0. We seek to obtain the worst-case
optimal submodular extension by making gT (s) same
as the objective of (P-LP) as T → 0. Since at T = 1,
problems (34) and (13) are equivalent, this gives us the
worst-case optimal extension for our problem (13) as
well.
The question now becomes how to recover the worstcase optimal submodular extension using E(y). The
following propositions answers this question.
Proposition 2. The worst-case optimal submodular
extension for Potts model is given by FP otts (A) =
PL
i=1 Fi (A), where
Fi (A) =

X

φa (i)[|A ∩ {vai }| = 1]+

a

X
(a,b)∈N

wab
· [|A ∩ {vai , vbi }| = 1]
2

(16)

Also, E(y) in (P-LP) is the Lovasz extension of FP otts .
(Proof in appendix)
Proposition 2 paves the way for us to identify the worstcase optimal extension for hierarchical Potts model,
which we discuss in the following section.

6

Hierarchical Potts

Potts model imposes the same penalty for unequal assignment of labels to neighbouring variables, regardless
of the label dissimilarity. A more natural approach is
to vary the penalty based on how different the labels
are. A hierarchical Potts model permits this by specifying the distance between labels using a tree with the
following properties:

Figure 4: An hierarchical Potts model instance illustrating
notations with 2 meta-labels (blue) and 4 labels (yellow).
All labels are at the same level. r = 2, that is, edge-length
decreases by 2 at each level. Also, distance between labels 1
and 3 is d(1, 3) = 0.5 + 1 + 1 + 0.5 = 3.
1. The vertices are of two types: (i) the leaf nodes
representing labels, and (ii) the non-leaf nodes,
except the root, representing meta-labels.
2. The lengths of all the edges from a parent to its
children are the same.
3. The lengths of the edges along any path from the
root to a leaf decreases by a factor of at least r ≥ 2
at each step.
4. The metric distance between nodes of the tree is
the sum of the edge lengths on the unique path
between them.
A subtree T of an hierarchical Potts model is a tree
comprising all the descendants of some node v (not
root). Given a subtree T , lT denotes the length of the
tree-edge leading upward from the root of T and L(T )
denotes the set of leaves of T . We call the leaves of the
tree as labels and all other nodes of the tree expect the
root as meta-labels. Figure 4 illustrates the notations
in the context of a hierarchical Potts model.
Tightest LP Relaxation We use the same indicator
variables yai that were employed
P in the LP relaxation of
Potts model. Let ya (T ) = i∈L(T ) yai . The following
LP relaxation is the tightest known for hierarchical
Potts model in the worst-case, assuming the Unique
Games Conjecture to be true [Manokaran et al., 2008]
XX
e
(T-LP) min E(y)
=
φa (i)yai +
y

X

a

i

wab

X

(a,b)∈N

such that

lT · |ya (T ) − yb (T )|

T

y ∈ ∆.

(17)

The set ∆ is the same domain as defined in equation
(57). We rewrite this LP relaxation using indicator
variables zai for all labels and meta-labels as
(T-LP-FULL)

e
min E(z)
such that

z ∈ ∆0

(18)

Worst-case Optimal Submodular Extensions for Marginal Estimation

where ∆0 is the convex hull of the vectors satisfying
X
zai = 1, zai ∈ {0, 1} ∀a ∈ X , i ∈ L (19)
i∈L

and zai =

X

zaj . ∀a ∈ X , i ∈ R − L

(20)

j∈L(Ti )

The details of the new relaxation (T-LP-FULL) can be
found in the appendix.
Set Encoding For any variable Xa , let the set of
possible assignment of labels and meta-labels be the
set Va = {va1 , . . . , vaM }, where M is the total number
of nodes in the tree except the root. Our ground set is
V = ∪N
a=1 Va of size N · M .
A consistent labeling of a variable assigns it one label,
and all meta-labels on the path from root to the label.
Let us represent the set of consistent assignments for
Xa by the set Pa = {pa1 , . . . , paL }, where pai is the
collection of elements from Va for label i and all metalabels on the path from root to label i.
The set of valid labelings A ⊆ V assigns each variable
exactly one consistent label. This constraint can be
formally written as M = ∩N
a=1 Ma where Ma has
exactly one element from Pa .
Let s0ai be the sum of the components of s corresponding
to the elements of pai , that is,
X
s0ai =
st .
(21)
t∈pai

Using our encoding scheme, we rewrite problem (8) as:
min
s∈EP (F )

N
X

log

a=1

L
X

exp(−s0ai ).

(22)

i=1

s∈EP (F )

gT (s) =

N
X

T · log

a=1

L
X
i=1

exp(−

s0ai
).
T

Proposition 4. The worst-case optimal submodular extension
hierarchical Potts model is given by
Pfor
M
Fhier (A) = i=1 Fi (A), where
Fi (A) =

X

φ0a (i)[|A ∩ {vai }| = 1]+

a

X

wab · lTi · [|A ∩ {vai , vbi }| = 1]

e
Also, E(z)
in (T-LP-FULL) is the Lovasz extension of
Fhier . (Proof in appendix)
Since any finite metric space can be probabilistically
approximated by mixture of tree metric [Bartal, 1996],
the worst-case optimal submodular extension for metric
energies can be obtained using Fhier . Note that Fhier
reduces to FP otts for Potts model. One can see this by
considering the Potts model as a star-shaped tree with
edge weights as 0.5.

7

Fast Conditional Gradient
Computation for Dense CRFs

Dense CRF Energy Function A dense CRF is
specified by the following energy function
X
X X
E(x) =
φa (xa ) +
φab (xa , xb ). (26)

− min0 f (z)

(24)

a∈X b∈X ,b6=a

Note that every random variable is a neighbour of
every other random variable in a dense CRF. Similar
to previous work [Koltun and Krahenbuhl, 2011], we
consider the pairwise potentials to be to be Gaussian,
that is,
X
(m)
φ(i, j) = µ(i, j)
w(m) k(fa(m) , fb ),
(27)
m
(m)
k(fa(m) , fb )

Proposition 3. In the limit T → 0, problem (52) for
hierarchical Potts energies becomes:

(25)

(a,b)∈N

(23)

Worst-case Optimal Submodular Extension
The following proposition connects the marginal estimation problem (8) with LP relaxations:

z∈∆

The above problem is equivalent to an LP relaxation
of the corresponding MAP estimtation problem (see
Remark 3 in appendix). Hence, gT (s) becomes the
objective function of an LP relaxation in the limit
e
T → 0. We seek to make this objective same as E(z)
of (T-LP-FULL) in the limit T → 0. The question
now becomes how to recover the worst-case optimal
e
submodular extension from E(z).

a∈X

Marginal Estimation with Temperature Similar to Potts model, we now introduce a temperature
parameter T > 0 to problem (22). The transformed
problem becomes

min

(Proof in appendix).


= exp

−||fa − fb ||2
2


.

(28)

The term µ(i, j) is known as label compatibility function
between labels i and j. Potts model and hierarchical
Potts models are examples of µ(i, j). The other term
is a mixture of Gaussian kernels k(., .) and is called
(m)
the pixel compatibility function. The terms fa are
features that describe the random variable Xa . In
practice, similar to [Koltun and Krahenbuhl, 2011], we

Pankaj Pansari1,2 , Chris Russell

2,3

, M. Pawan Kumar1,2

use x, y coordinates and RGB values associated to a
pixel as its features.

However, using the equivalence of relaxed LP objectives
and the Lovasz extension of submodular extensions in
proposition 6, we are able to compute s∗ in O(N L) time.
Specifically, we use the algorithm of Ajanthan et al.
[2017], which provides an efficient filtering procedure to
compute the subgradient of the LP relaxation objective
E(y) of (P-LP).
Proposition 5. Computing the subgradient of E(y)
in (P-LP) is equivalent to computing the conditional
gradient for the submodular function FP otts .
(Proof in appendix).
A similar observation can be made in case of hierarchical Potts model. Hence we have the first practical
algorithm to compute upper bound of log-partition
function of a dense CRF for Potts and metric energies.

8

Experiments

Using synthetic data, we show that our upper-bound
compares favorably with TRW for both Potts and hierarchical Potts models. For comparison, we restrict
ourselves to sparse CRFs, as the code available for TRW
does not scale well to dense CRFs. We also perform
stereo matching using dense CRF models and compare our results with the mean-field-based approach of
[Koltun and Krahenbuhl, 2011]. All experiments were
run on a x86-64, 3.8GHz machine with 16GB RAM. In
this section, we refer to our algorithm as Submod and
mean field as MF.
8.1

Upper-bound Comparison using
Synthetic Data
Data We generate lattices of size 100 × 100, where
each lattice point represents a variable taking one of
20 labels. The pairwise relations of the sparse CRFs
are defined by 4-connected neighbourhoods. The unary
potentials are uniformly sampled in the range [0, 10].
We consider (a) Potts model and (b) hierarchical Potts
models with pairwise distance between labels given by
the trees of figure 5. The pairwise weights are varied
in the range {1, 2, 5, 10}. We compare the results of
our worst-case optimal submodular extension with an

(a) Tree 1

(b) Tree 2

Figure 5: The hierarchical Potts models defining pairwise
distance among 20 labels used for upper-bound comparison
with TRW. Blue nodes are the meta-labels and yellow nodes
are labels. All the edges at a particular level have the same
edge weights. The sequence of weights from root level to leaf
level is 1, 0.5 for tree 1 and 1, 1, 0.5 for tree 2. The yellow
node is shown to clump together 4 and 5 leaf nodes for tree
1 and 2 respectively.
s

φ1(1)

1-1
φ1(3)

1-2

φ2(1)

2-1

φ1(2)
1-3

φ2(3)
2-3

2-2
φ2(2)

t

Figure 6: An st-graph specifying the alternate submodular
extension for Potts model for 2 variables with 3 labels each
and connected to each other. The convention used is same
as in figure 3. Each dotted red arc has weight w12 /2. This
alternate extension was also used to derive the extension
for hierarchical Potts model.

4.0
(Submodular bound - TRW bound)/|TRW bound|

Algorithm 1 assumes that the conditional gradient s∗ in
step 3 can be computed efficiently. This is certainly not
the case for dense CRFs, since computing s∗ involves
N L function evaluations of the submodular extension
F , where N is the number of variables, and L is the
number of labels. Each F evaluation has complexity
O(N ) using the efficient Gaussian filtering algorithm
of [Koltun and Krahenbuhl, 2011]. However, computation of s∗ would still be O(N 2 ) this way, which is
clearly impractical for computer-vision applications
where N ∼ 105 − 106 .

Potts Optimal Extension
Potts Alternate Extension
Hierarchical Tree 1 Optimal Extension
Hierarchical Tree 1 Alternate Extension
Hierarchical Tree 2 Optimal Extension
Hierarchical Tree 2 Alternate Extension

3.5
3.0
2.5
2.0
1.5
1.0
0.5
0.0
0.5
1

2

3

4

5
6
Weight

7

8

9

10

Figure 7: Upper-bound comparison using synthetic
data. The plot shows the ratio (Submod bound - TRW
bound)/|TRW bound| averaged over 100 unary instances as
a function of pairwise weights using the worst-case optimal
and alternate extension for Potts and hierarchical Potts
models. We observe that the worst-case optimal extension
(solid) results in tighter bounds as compared to the respective
alternate extensions (dotted). Also, the worst-case optimal
extension bounds are in similar range as the TRW bounds.
Figure best viewed in color.

Worst-case Optimal Submodular Extensions for Marginal Estimation

alternate submodular extension as given in figure 2.
Method For our algorithm, we use the standard
schedule γ = 2/(k + 2) to obtain step size γ at iteration k. We run our algorithm till convergence - 100
iterations suffice for this. The experiments are repeated
for 100 randomly generated unaries for each model and
each weight. For TRW, we used the MATLAB toolbox
of [Domke, 2013]. The baseline code does not optimise
over tree distributions. We varied the edge-appearance
probability in trees over the range [0.1 - 0.5] and found
0.5 to give tightest upper bound.
Results We plot the ratio of the normalised difference of the upper bound values of our method with
TRW as a function of pairwise weights. The ratios are
averaged over 100 instances of unaries. Figure 7 shows
the plots for Potts and hierarchical Potts models for
the worst-case optimal and alternate extension. We
find that the optimal extension (solid) results in tighter
upper-bounds than the alternate extension (dotted) for
both models. To see the reason for this, we observe
that the representation of the submodular function
using figure 6 necessitates that φa (i) be non-negative.
This implies that F (A) values are larger for the worstcase optimal extension of figure 3 as compared to the
alternate extension. Hence the minimisation problem
8 has the same objective function g(s) for both cases
but the domain EP (F ) of equation (2) is larger for the
optimal extension, thereby resulting in better minima.
Figure 7 also indicates that our algorithm with optimal
extension provides similar range of upper bound as
TRW, thereby providing empirical justification of our
method. Note that the TRW upper bound has to be
tighter than our method. This is because the TRW
makes use of the standard LP relaxation [Chekuri et al.,
2004] which involves marginal variables for nodes as
well as edges. On the other hand, our method makes
use of the LP relaxation proposed by Kleinberg and
Tardos [2002] which involves marginal variables only
for nodes. The standard LP relaxation is tighter than
Kleinberg-Tardos relaxation, and hence TRW results in
better approximation. However, TRW does not scale
well with neighborhood size, thereby prohibiting its use
in dense CRFs.
8.2

Stereo Matching using Dense CRFs

Data We demonstrate the benefit our algorithm for
stereo matching on images extracted from the Middlebury stereo matching dataset [Scharstein et al., 2001].
We use dense CRF models with Potts compatibility
term and Gaussian pairwise potentials. The unary
terms are obtained using the absolute difference matching function of [Scharstein et al., 2001].

Method We use the implementation of mean-field
algorithm for dense CRFs of [Koltun and Krahenbuhl,
2011] as our baseline. For our algorithm, we make use
of the modified Gaussian filtering implementation for
dense CRFs by [Ajanthan et al., 2017] to compute the
conditional gradient at each step. The step size γ at
each iteration is selected by doing line search. We run
our algorithm till 100 iterations, since the visual quality
of the solution does not show much improvement beyond this point. We run mean-field up to convergence,
with a threshold of 0.001 for change in KL-divergence.
Results Figure 8 shows some example solutions obtained by picking the label with maximum marginal
probability for each variable for mean-field and for our
algorithm. We also report the time and energy values
of the solution for both methods. Though we are not
performing MAP estimation, energy values give us a
quantitative indication of the quality of solutions. For
the full set of 21 image pairs (2006 dataset), the average
ratio of the energies of the solutions from our method
compared to mean-field is 0.943. The avearge time
ratio is 10.66. We observe that our algorithm results
in more natural looking stereo matching results with
lower energy values for all images. However, mean-field
runs faster than our method for each instance.

9

Discussion

We have established the relation between submodular
extension for the Potts model and the LP relaxation
for MAP estimation using Lovasz extension. This allowed us to identify the worst-case optimal submodular
extension for Potts as well as the general metric labeling problems. It is worth noting that it might still be
possible to obtain an improved submodular extension
for a given problem instance. The design of a computationally feasible algorithm for this task is an interesting
direction of future research. While our current work has
focused on pairwise graphical models, it can be readily applied to high-order potentials by considering the
corresponding LP relaxation objective as the Lovasz extension of a submodular extension. The identification
of such extensions for popular high-order potentials
such as the P n Potts model or its robust version could
further improve the accuracy of important computer
vision applications such as semantic segmentation.

Pankaj Pansari1,2 , Chris Russell

(a) Venus GT

(a) Cones GT

(b) MF solution

(c) Submod solution

60.32s, 1.83e+07

469.75s, 1.55e+07

(b) MF solution

(c) Submod solution

239.14s, 2.68e+07

1082.72s, 1.27e+07

2,3

, M. Pawan Kumar1,2

(a) Tsukuba GT

(a) Teddy GT

(b) MF solution

(c) Submod solution

14.93s, 8.21e+06

215.22s, 4.12e+06

(b) MF solution

(c) Submod solution

555.30s, 2.36e+07

1257.86s, 1.58e+07

Figure 8: Stereo matching using dense CRFs with Potts compatibility and Gaussian pairwise potentials. We compare our
solution with the mean-field algorithm of Koltun and Krahenbuhl [2011]. We observe that our method gives better-looking
solutions with lower energy value at the cost of higher computational time.

References
Ajanthan, T., Desmaison, A., Bunel, R., Salzmann, M.,
Torr, P., and Kumar, M. (2017). Efficient continuous
relaxations for dense crf. In CVPR.
Bartal, Y. (1996). Probabilistic approximation of metric spaces and its algorithmic applications. In Foundations of Computer Science.
Bartal, Y. (1998). On approximating arbitrary metrices
by tree metrics. In ACM Symposium on Theory of
Computing.
Boykov, Y., Veksler, O., and Zabih, R. (2001). Fast
approximate energy minimization via graph cuts.
PAMI.
Chekuri, C., Khanna, S., Naor, J., and Zosin, L. (2004).
A linear programming formulation and approximation algorithms for the metric labeling problem.
SIAM Journal on Discrete Mathematics.
Djolonga, J. and Krause, A. (2014). From map to
marginals: Variational inference in bayesian submodular models. In NIPS.
Domke, J. (2013). Learning graphical model parameters
with approximate marginal inference. PAMI.
Edmonds, J. (1970). Submodular functions, matroids,
and certain polyhedra. Combinatorial Optimization
— Eureka, You Shrink!
Frank, M. and Wolfe, P. (1956). An algorithm for
quadratic programming. Naval research logistics
quarterly.
Kleinberg, J. and Tardos, E. (2002). Approximation
algorithms for classification problems with pairwise
relationships: Metric labeling and markov random
fields. IEEE Symposium on the Foundations of Computer Science.
Koltun, V. and Krahenbuhl, P. (2011). Efficient inference in fully connected crfs with gaussian edge

potentials. NIPS.
Kumar, M., Veksler, O., and Torr, P. (2011). Improved
moves for truncated convex models. JMLR.
Manokaran, R., Naor, J., Raghavendra, P., and
Schwartz, R. (2008). Sdp gaps and ugc hardness
for multiway cut, 0-extension, and metric labeling.
In ACM Symposium on Theory of Computing.
Scharstein, D., Szeliski, R., and Zabih, R. (2001). A
taxonomy and evaluation of dense two-frame stereo
correspondence algorithms. In Stereo and MultiBaseline Vision.
Wainwright, M., Jaakkola, T., and Willsky, A. (2005).
A new class of upper bounds on the log partition
function. IEEE Transactions on Information Theory.
Zhang, J., Djolonga, J., and Krause, A. (2015). Higherorder inference for multi-class log-supermodular models. In ICCV.

Worst-case Optimal Submodular Extensions for Marginal Estimation

Appendix
1

Proofs for Potts Model Extension

Remark 1

We show using induction over the number of variables that with 1-of-L encoding for Potts,

X

exp(−s(A)) =

N X
L
Y

exp(−sai ).

(29)

a=1 i=1

A∈M

Proof. Let t be the number of variables, V t be the corresponding ground set and Mt be the sets corresponding
to valid labelings. Equation (29) clearly holds for t = 1.
Let us assume that the relation holds for t = N , that is,

X

N

exp(−s(A )) =

N X
L
Y

exp(−sai )

(30)

a=1 i=1

AN ∈MN

For t = N + 1,

X

exp(−s(AN +1 )) =

L
X

X

exp(−s(AN ) − sN +1,i )

i=1 AN ∈MN

AN +1 ∈MN +1

=

L
X
i=1

=

L
X

exp(−s(AN ))

AN ∈MN

exp(−sN +1,i )

N
+1 X
L
Y

N X
L
Y

exp(−sai )

a=1 i=1

i=1

=

X

exp(−sN +1,i )

exp(−sai )

(31)

a=1 i=1


Remark 2 Given any submodular extension F (.) of a Potts energy function E(.), its Lovasz extension f (.)
defines an LP relaxation of the MAP problem for E(.) as
min f (y).
y∈∆

(32)

Proof. By definition of a submodular extension and the Lovasz extension, E(x) = F (Ax ) = f (1Ax ) for all valid
labelings x. Also, from property 1, f (y) is maximum of linear functions. Hence, f (y) is a piecewise linear
relaxation of E(x).
The domain ∆ is a polytope formed by union of N probability simplices
∆ = {ya ∈ RL |ya  0 and h1, ya i = 1}

(33)

With objective as maximum of linear functions and domain as a polytope, we have an LP relaxation of the
corresponding MAP problem.


Pankaj Pansari1,2 , Chris Russell

2,3

, M. Pawan Kumar1,2

Proposition 6. In the limit T → 0, the following problem for Potts energies
min
s∈EP (F )

gT (s) =

N
X

T · log

a=1

L
X

exp(−

i=1

sai
).
T

(34)

becomes
− min f (y).
y∈∆

(35)

Proof. In the limit of T → 0, we can rewrite the above problem as
N
X

min
s∈EP (F )

a=1

max(−sai ).
i

(36)

In vector form, the problem becomes
min

max −hy, si

s∈EP (F ) y∈∆

(37)

= − max minhy, si

(38)

∆ = {ya ∈ RL |ya  0 and h1, ya i = 1}

(39)

s∈EP (F ) y∈∆

∆ is the union of N probability simplices:

where ya is the component of y corresponding to the a-th variable. By the minimax theorem for LP, we can
reorder the terms:
− min max hy, si
(40)
y∈∆ s∈EP (F )

Recall that maxs∈EP (F ) hy, si is the value of the Lovasz extension of F at y, that is, f (y). Hence, as T → 0, the
marginal inference problem converts to minimising the Lovasz extension under the simplices constraint:
− min f (y)
y∈∆

(41)


Proposition 7. The objective function E(y) of the LP relaxation (P-LP) is the Lovasz extension of FP otts (A) =
PL
i=1 Fi (A), where
X
Fi (A) =
φa (i)[|A ∩ {vai }| = 1]+
a

X
(a,b)∈N

wab
· [|A ∩ {vai , vbi }| = 1].
2

(42)

Proof. Since FP otts is sum of Ising models Fi , we first focus on a particular label i and then generalize. Consider
a graph with only two variables Xa and Xb with an edge between them. The ground set in this case is {vai , vbi }.
Let the corresponding relaxed indicator variables be y = {yaj , ybj }, such that yai , ybi ∈ [0, 1] and assume yai > ybi .
The Lovasz extension is:

f (y) = yai · [Fi ({vai }) − Fi ({})] + ybi · [Fi ({vai , vbi }) − Fi ({vai })]


wab 
wab 
= yai · [ φa (j) +
− 0] + ybi · [(φa (j) + φb (j)) − φa (j) +
]
2
2
wab
= φa (j) · yai + φb (j) · ybi +
· (yai − ybi )
2

(43)

Worst-case Optimal Submodular Extensions for Marginal Estimation

In general for both orderings of yab and ybi , we can write
wab
· |yai − ybi |
2
Extending Lovasz extension (equation (44)) to all variables and labels gives E(y) in (P-LP).
f (y) = φa (j) · yai + φb (j) · ybi +

2

(44)


Proofs for Hierarchical Potts Model Extension

Transformed Tightest LP Relaxation We take (T-LP) and rewrite it using indicator variables for all labels
and meta-labels. Let R denote the set of all labels and meta-labels, that is, all nodes in the tree apart from the
root. Also, let L denote the set of labels, that is, the leaves of the tree. Let Ti denote the subtree which is rooted
at the i-th node. We introduce an indicator variable zai ∈ {0, 1}, where
(
yai
if i ∈ L
zai =
(45)
ya (Ti )
if i ∈ R − L
We need to extend the definition of unary potentials to the expanded label space as follows:
(
φa (i)
if i ∈ L
where φ0a (i) =
0
if i ∈ R − L

(46)

We can now rewrite problem (T-LP) in terms of new indicator variables zai :
XX
e
(T-LP-FULL) min E(z)
=
φ0a (i) · zai +
i∈R a∈X

X X

wab · lTi · |zai − zbi |

i∈R (a,b)∈N

such that

z ∈ ∆0

(47)

where ∆0 is the convex hull of the vectors satisfying
X
zai = 1, zai ∈ {0, 1} ∀a ∈ X , i ∈ L

(48)

i∈L

and zai =

X

zaj . ∀a ∈ X , i ∈ R − L

(49)

j∈L(Ti )

Constraint (49) ensures consistency among labels and meta-labels, that is, if a label is assigned then all the
meta-labels which lie on the path from the root to the label should be assigned as well. We are now going to
identify a suitable set encoding and the worst-case optimal submodular extension using (T-LP-FULL).
Remark 3 Given any submodular extension F (.) of a hierachical Potts energy function E(.), its Lovasz extension
defines an LP relaxation of the corresponding MAP estimation problem as
min f (z).

z∈∆0

(50)

Proof. By definition of a submodular extension and the Lovasz extension, E(x) = F (Ax ) = f (1Ax ) for all valid
labelings x. Also, from property 1, f (y) is maximum of linear functions. Hence, f (y) is a piecewise linear
relaxation of E(x).
We can write the domain ∆0 as
∆0 = {ya ∈ RM |ya  0, h1, yalabel i = 1, ya (pai ) = 1 or ya (pai ) = 0∀i ∈ [1, L]}

(51)

where ya is the component of y corresponding to the a-th variable, yalabel is the component of ya corresponding
to the L labels, and ya (pai ) is the component of ya corresponding to the elements of pai .
Since ∆0 is defined by linear equalities and inequalities, it is a polytope. With objective as maximum of linear
functions and domain as a polytope, we have an LP relaxation of the corresponding MAP problem.


Pankaj Pansari1,2 , Chris Russell

2,3

, M. Pawan Kumar1,2

Proposition 8. In the limit T → 0, the following problem for hierarchical Potts energies

min
s∈EP (F )

gT (s) =

N
X

T · log

a=1

L
X

exp(−

i=1

s0ai
).
T

(52)

becomes:
− min0 f (z).

(53)

z∈∆

Proof. In the limit of T → 0, we can rewrite the above problem as
N
X

min
s∈EP (F )

a=1

max(−s0ai ).

(54)

i

In vector form, the problem becomes
min

max −hz, s0 i

(55)

s∈EP (F ) z∈∆

= − max minhz, s0 i

(56)

s∈EP (F ) z∈∆

where ∆ = {za ∈ RL |za  0 and h1, za i = 1}

(57)
0

where za is the component of z corresponding to the a-th variable. We can unpack s using
X
s0ai =
st .

(58)

t∈pai

and rewrite problem (56) as
− max

min hy, si

s∈EP (F ) y∈∆0

(59)

The new constraint set ∆0 ensures that the binary entries of labels and meta-labels is consistent:
where ∆0 = {ya ∈ RM |ya  0, h1, yalabel i = 1,
ya (pai ) = 1 or ya (pai ) = 0∀i ∈ [1, L]}

(60)

where ya is the component of y corresponding to the a-th variable, yalabel is the component of ya corresponding
to the L labels, and ya (pai ) is the component of ya corresponding to the elements of pai .
By the minimax theorem for LP, we can reorder the terms:
− min0 max hy, si
y∈∆ s∈EP (F )

(61)

Recall that maxs∈EP (F ) hy, si is the value of the Lovasz extension of F at y, that is, f (y). Hence, as T → 0, the
marginal inference problem converts to minimising the Lovasz extension under the constraints ∆0 :
− min0 f (y).
y∈∆

(62)


e
Proposition 9. The objective function E(z)
of (T-LP-FULL) is the Lovasz extension of Fr−HST (A) =
PM
F
(A),
where
i
i=1
X
φ0a (i)[|A ∩ {vai }| = 1]+
Fi (A) =
a

X
(a,b)∈N

wab · lTi · [|A ∩ {vai , vbi }| = 1].

(63)

Worst-case Optimal Submodular Extensions for Marginal Estimation

Proof. We observe that Fr−HST is of exactly the same form as FP otts , except that the Ising models Fi are defined
over not just labels, but meta-labels as well. Using the same logic as in the proof of proposition 7, each Fi is the
Lovasz extension of


X
X
ei (z) = 
E
φ0a (i) · zai +
wab · lTi · |zai − zbi |
(64)
a∈X

and the results follows.

(a,b)∈N



