11institutetext: Department of Engineering Science, University of Oxford
11email:  {alban, rudy<EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: Microsoft Research
22email<EMAIL_ADDRESS>
# Efficient Continuous Relaxations for Dense CRF

Alban Desmaison1 Joint first authors Rudy Bunel††footnotemark: 1 Pushmeet
Kohli2 Philip H.S. Torr1 M. Pawan Kumar1

###### Abstract

Dense conditional random fields (CRF) with Gaussian pairwise potentials have
emerged as a popular framework for several computer vision applications such
as stereo correspondence and semantic segmentation. By modeling long-range
interactions, dense CRFs provide a more detailed labelling compared to their
sparse counterparts. Variational inference in these dense models is performed
using a filtering-based mean-field algorithm in order to obtain a fully-
factorized distribution minimising the Kullback-Leibler divergence to the true
distribution. In contrast to the continuous relaxation-based energy
minimisation algorithms used for sparse CRFs, the mean-field algorithm fails
to provide strong theoretical guarantees on the quality of its solutions. To
address this deficiency, we show that it is possible to use the same filtering
approach to speed-up the optimisation of several continuous relaxations.
Specifically, we solve a convex quadratic programming (QP) relaxation using
the efficient Frank-Wolfe algorithm. This also allows us to solve difference-
of-convex relaxations via the iterative concave-convex procedure where each
iteration requires solving a convex QP. Finally, we develop a novel divide-
and-conquer method to compute the subgradients of a linear programming
relaxation that provides the best theoretical bounds for energy minimisation.
We demonstrate the advantage of continuous relaxations over the widely used
mean-field algorithm on publicly available datasets.

###### Keywords:

Energy minimisation, Dense CRF, Inference, Linear Programming, Quadratic
Programming

##  1 Introduction

Discrete pairwise conditional random fields (CRFs) are a popular framework for
modelling several problems in computer vision. In order to use them in
practice, one requires an energy minimisation algorithm that obtains the most
likely output for a given input. The energy function consists of a sum of two
types of terms: unary potentials that depend on the label for one random
variable at a time and pairwise potentials that depend on the labels of two
random variables.

Traditionally, computer vision methods have employed sparse connectivity
structures, such as 4 or 8 connected grid CRFs. Their popularity lead to a
considerable research effort in efficient energy minimisation algorithms. One
of the biggest successes of this effort was the development of several
accurate continuous relaxations of the underlying discrete optimisation
problem [1, 2]. An important advantage of such relaxations is that they lend
themselves easily to analysis, which allows us to compare them theoretically
[3], as well as establish bounds on the quality of their solutions [4].

Recently, the influential work of Krähenbühl and Koltun [5] has popularised
the use of dense CRFs, where each pair of random variables is connected by an
edge. Dense CRFs capture useful long-range interactions thereby providing
finer details on the labelling. However, modeling long-range interactions
comes at the cost of a significant increase in the complexity of energy
minimisation. In order to operationalise dense CRFs, Krähenbühl and Koltun [5]
made two key observations. First, the pairwise potentials used in computer
vision typically encourage smooth labelling. This enabled them to restrict
themselves to the special case of Gaussian pairwise potentials introduced by
Tappen et al. [6]. Second, for this special case, it is possible to obtain a
labelling efficiently by using the mean-field algorithm [7]. Specifically, the
message computation required at each iteration of mean-field can be carried
out in $O(N)$ operations where $N$ is the number of random variables (of the
order of hundreds of thousands). This is in contrast to a naïve implementation
that requires $O(N^{2})$ operations. The significant speed-up is made possible
by the fact that the messages can be computed using the filtering approach of
Adams et al. [8].

While the mean-field algorithm does not provide any theoretical guarantees on
the energy of the solutions, the use of a richer model, namely dense CRFs,
still allows us to obtain a significant improvement in the accuracy of several
computer vision applications compared to sparse CRFs [5]. However, this still
leaves open the intriguing possibility that the same filtering approach that
enabled the efficient mean-field algorithm can also be used to speed-up energy
minimisation algorithms based on continuous relaxations. In this work, we show
that this is indeed possible.

In more detail, we make three contributions to the problem of energy
minimisation in dense CRFs. First, we show that the conditional gradient of a
convex quadratic programming (QP) relaxation [1] can be computed in $O(N)$
complexity. Together with our observation that the optimal step-size of a
descent direction can be computed analytically, this allows us to minimise the
QP relaxation efficiently using the Frank-Wolfe algorithm [9]. Second, we show
that difference-of-convex (DC) relaxations of the energy minimisation problem
can be optimised efficiently using an iterative concave-convex procedure
(CCCP). Each iteration of CCCP requires solving a convex QP, for which we can
once again employ the Frank-Wolfe algorithm. Third, we show that a linear
programming (LP) relaxation [2] of the energy minimisation problem can be
optimised efficiently via subgradient descent. Specifically, we design a novel
divide-and-conquer method to compute the subgradient of the LP. Each
subproblem of our method requires one call to the filtering approach. This
results in an overall run-time of $O(N\log(N))$ per iteration as opposed to an
$O(N^{2})$ complexity of a naïve implementation. It is worth noting that the
LP relaxation is known to provide the best theoretical bounds for energy
minimisation with metric pairwise potentials [2].

Using standard publicly available datasets, we demonstrate the efficacy of our
continuous relaxations by comparing them to the widely used mean-field
baseline for dense CRFs.

##  2 Related works

Krähenbühl and Koltun popularised the use of densely connected CRFs at the
pixel level [5], resulting in significant improvements both in terms of the
quantitative performance and in terms of the visual quality of their results.
By restricting themselves to Gaussian edge potentials, they made the
computation of the message in parallel mean-field feasible. This was achieved
by formulating message computation as a convolution in a higher-dimensional
space, which enabled the use of an efficient filter-based method [8].

While the original work [5] used a version of mean-field that is not
guaranteed to converge, their follow-up paper [10] proposed a convergent mean-
field algorithm for negative semi-definite label compatibility functions.
Recently, Baqué et al. [11] presented a new algorithm that has convergence
guarantees in the general case. Vineet et al. [12] extended the mean-field
model to allow the addition of higher-order terms on top of the dense pairwise
potentials, enabling the use of co-occurence potentials [13] and $P^{n}$-Potts
models [14].

The success of the inference algorithms naturally lead to research in learning
the parameters of dense CRFs. Combining them with Fully Convolutional Neural
Networks [15] has resulted in high performance on semantic segmentation
applications [16]. Several works [17, 18] showed independently how to jointly
learn the parameters of the unary and pairwise potentials of the CRF. These
methods led to significant improvements on various computer vision
applications, by increasing the quality of the energy function to be minimised
by mean-field.

Independently from the mean-field work, Zhang et al. [19] designed a different
set of constraints that lends itself to a QP relaxation of the original
problem. Their approach is similar to ours in that they use continuous
relaxation to approximate the solution of the original problem but differ in
the form of the pairwise potentials. The algorithm they propose to solve the
QP relaxation has linearithmic complexity while ours is linear. Furthermore,
it is not clear whether their approach can be easily generalised to tighter
relaxations such as the LP.

Wang et al. [20] derived a semi-definite programming relaxation of the energy
minimisation problem, allowing them to reach better energy than mean-field.
Their approach has the advantage of not being restricted to Gaussian pairwise
potentials. The inference is made feasible by performing low-rank
approximation of the Gram matrix of the kernel, instead of using the filter-
based method. However, while the complexity of their algorithm is the same as
our QP or DC relaxation, the runtime is significantly higher. Furthermore,
while the SDP relaxation has been shown to be accurate for repulsive pairwise
potentials (encouraging neighbouring variables to take different labels) [21],
our LP relaxation provides the best guarantees for attractive pairwise
potentials [2].

In this paper, we use the same filter-based method [8] as the one employed in
mean-field. We build on it to solve continuous relaxations of the original
problem that have both convergence and quality guarantees. Our work can be
viewed as a complementary direction to previous research trends in dense CRFs.
While [10, 11, 12] improved mean-field and [17, 18] learnt the parameters, we
focus on the energy minimisation problem.

##  3 Preliminaries

Before describing our methods for energy minimisation on dense CRF, we
establish the necessary notation and background information.

####  3.0.1 Dense CRF Energy Function.

We define a dense CRF on a set of $N$ random variables
$\mathcal{X}=\left\\{X_{1},\dots,X_{N}\right\\}$ each of which can take one
label from a set of $M$ labels
$\mathcal{L}=\left\\{l_{1},\dots\,l_{M}\right\\}$. To describe a labelling, we
use a vector $\mathbf{x}$ of size $N$ such that its element $x_{a}$ is the
label taken by the random variable $X_{a}$. The energy associated with a given
labelling is defined as:

$E(\mathbf{x})=\sum_{a=1}^{N}\phi_{a}(x_{a})+\sum_{a=1}^{N}\sum_{\begin{subarray}{c}b=1\\\
b\neq a\end{subarray}}^{N}\psi_{a,b}(x_{a},x_{b}).$ (1)

Here, $\phi_{a}(x_{a})$ is called the unary potential for the random variable
$X_{a}$ taking the label $x_{a}$. The term $\psi_{a,b}(x_{a},x_{b})$ is called
the pairwise potential for the random variables $X_{a}$ and $X_{b}$ taking the
labels $x_{a}$ and $x_{b}$ respectively. The energy minimisation problem on
this CRF can be written as:

$\mathbf{x}^{\star}=\operatorname*{\arg\\!\min}_{\mathbf{x}}E(\mathbf{x}).$
(2)

####  3.0.2 Gaussian Pairwise Potentials.

Similar to previous work [5], we consider arbitrary unary potentials and
Gaussian pairwise potentials. Specifically, the form of the pairwise
potentials is given by:

$\psi_{a,b}(i,j)=\mu(i,j)\sum_{m}w^{(m)}k(\mathbf{f}^{(m)}_{a},\mathbf{f}^{(m)}_{b}),$
(3)
$k(\mathbf{f}_{a},\mathbf{f}_{b})=\exp\left(\frac{-\|\mathbf{f}_{a}-\mathbf{f}_{b}\|^{2}}{2}\right)$
(4)

We refer to the term $\mu(i,j)$ as a label compatibility function between the
labels $i$ and $j$. An example of a label compatibility function is the Potts
model, where $\mu_{\text{potts}}(i,j)=[i\neq j]$, that is $\mu_{potts}(i,j)=1$
if $i\neq j$ and 0 otherwise. Note that the label compatibility does not
depend on the image. The other term, called the pixel compatibility function,
is a mixture of gaussian kernels $k(\cdot,\cdot)$. The coefficients of the
mixture are the weights $w^{(m)}$. The $\mathbf{f}^{(m)}_{a}$ are the features
describing the random variable $X_{a}$. Note that the pixel compatibility does
not depend on the labelling. In practice, similar to [5], we use the position
and RGB values of a pixel as features.

####  3.0.3 IP Formulation.

We now introduce a formulation of the energy minimisation problem that is more
amenable to continuous relaxations. Specifically, we formulate it as an
Integer Program (IP) and then relax it to obtain a continuous optimisation
problem. To this end, we define the vector $\mathbf{y}$ whose components
$y_{a}(i)$ are indicator variables specifying whether or not the random
variable $X_{a}$ takes the label $i$. Using this notation, we can rewrite the
energy minimisation problem as an IP:

$\begin{split}\min\quad&\sum_{a=1}^{N}\sum_{i\in\mathcal{L}}\phi_{a}(i)y_{a}(i)+\sum_{a=1}^{N}\sum_{\begin{subarray}{c}b=1\\\
b\neq
a\end{subarray}}^{N}\sum_{i,j\in\mathcal{L}}\psi_{a,b}(i,j)y_{a}(i)y_{b}(j),\\\
\text{s.t. }&\sum_{i\in\mathcal{L}}y_{a}(i)=1\quad\forall a\in[1,N],\\\
&y_{a}(i)\in\\{0,1\\}\quad\forall a\in[1,N]\quad\forall i\in\mathcal{L}.\\\
\end{split}$ (5)

The first set of constraints model the fact that each random variable has to
be assigned exactly one label. The second set of constraints enforce the
optimisation variables $y_{a}(i)$ to be binary. Note that the objective
function is equal to the energy of the labelling encoded by $\mathbf{y}$.

####  3.0.4 Filter-based Method.

Similar to [5], a key component of our algorithms is the filter-based method
of Adams et al. [8]. It computes the following operation:

$\forall a\in[1,N],\quad
v^{\prime}_{a}=\sum_{b=1}^{N}k(\mathbf{f}_{a},\mathbf{f}_{b})v_{b},$ (6)

where $v_{a}^{\prime},v_{b}\in\mathbb{R}$ and $k(\cdot,\cdot)$ is a Gaussian
kernel. Performing this operation the naïve way would result in computing a
sum on $N$ elements for each of the $N$ terms that we want to compute. The
resulting complexity would be $\mathcal{O}(N^{2})$. The filter-based method
allows us to perform it approximately with $\mathcal{O}(N)$ complexity. We
refer the interested reader to [8] for details. The accuracy of the
approximation made by the filter-based method is explored in the Appendix 0.A.

##  4 Quadratic Programming Relaxation

We are now ready to demonstrate how the filter-based method [8] can be used to
optimise our first continuous relaxation, namely the convex quadratic
programming (QP) relaxation.

####  4.0.1 Notation.

In order to concisely specify the QP relaxation, we require some additional
notation. Similar to [10], we rewrite the objective function with linear
algebra operations. The vector $\bm{\phi}$ contains the unary terms. The
matrix $\bm{\mu}$ corresponds to the label compatibility function. The
Gaussian kernels associated with the $m$-th features are represented by their
Gram matrix
$\mathbf{K}^{(m)}_{a,b}=k(\mathbf{f}_{a}^{(m)},\mathbf{f}_{b}^{(m)})$. The
Kronecker product is denoted by $\otimes$. The matrix $\bm{\Psi}$ represents
the pairwise terms and is defined as follows:

$\bm{\Psi}=\bm{\mu}\otimes\left(\sum_{m}\mathbf{K}^{(m)}-\mathbf{I}_{N}\right),$
(7)

where $\mathbf{I}_{N}$ is the identity matrix. Under this notation, the IP (5)
can be concisely written as

$\begin{split}\min\quad&\bm{\phi}^{T}\mathbf{y}+\mathbf{y}^{T}\bm{\Psi}\mathbf{y},\\\
\text{ s.t. }\quad&\mathbf{y}\in\mathcal{I},\end{split}$ (8)

with $\mathcal{I}$ being the feasible set of integer solution, as defined in
equation (5).

####  4.0.2 Relaxation.

In general, IP such as (8) are NP-hard problems. Relaxing the integer
constraint on the indicator variables to allow fractional values between 0 and
1 results in the QP formulation. Formally, the feasible set of our
minimisation problem becomes:

$\mathcal{M}=\left\\{\mathbf{y}\quad\text{such that }\quad\begin{aligned}
\sum_{i\in\mathcal{L}}y_{a}(i)&=1\quad&&\forall a\in[1,N],\\\ y_{a}(i)&\geq
0&&\forall a\in[1,N],\forall i\in\mathcal{L}\end{aligned}\right\\}.$ (9)

Ravikumar and Lafferty [1] showed that this relaxation is tight and that
solving the QP will result in solving the IP. However, this QP is still NP-
hard, as the objective function is non-convex. To alleviate this difficulty,
Ravikumar and Lafferty [1] relaxed the QP minimisation to the following convex
problem:

$\begin{split}\min\quad&S_{cvx}(\mathbf{y})=(\bm{\phi}-\mathbf{d})^{T}\mathbf{y}+\mathbf{y}^{T}(\bm{\Psi}+\mathbf{D})\mathbf{y},\\\
\text{s.t. }\quad&\mathbf{y}\in\mathcal{M},\end{split}$ (10)

where the vector $\mathbf{d}$ is defined as follows

$d_{a}(i)=\sum_{\begin{subarray}{c}b=1\\\ b\neq
a\end{subarray}}^{N}\sum_{j\in\mathcal{L}}|\psi_{a,b}(i,j)|,$ (11)

and $\mathbf{D}$ is the square diagonal matrix with $\mathbf{d}$ as its
diagonal.

####  4.0.3 Minimisation.

We now introduce a new method based on the Frank-Wolfe algorithm [9] to
minimise problem (23). The Frank-Wolfe algorithm allows to minimise a convex
function $f$ over a convex feasible set $\mathcal{M}$. The key steps of the
algorithm are shown in Algorithm 1. To be able to use the Frank-Wolfe
algorithm, we need a way to compute the gradient of the objective function
(Step 3), a method to compute the conditional gradient (Step 4) and a strategy
to choose the step size (Step 5).

1:Get $\mathbf{y}^{0}\in\mathcal{M}$

2:while not converged do

3: Compute the gradient at $\mathbf{y}^{t}$ as $\mathbf{g}=\nabla
f(\mathbf{y}^{t})$

4: Compute the conditional gradient as
$\mathbf{s}=\operatorname*{\arg\\!\min}_{\mathbf{s}\in\mathcal{M}}\langle\mathbf{s},\mathbf{g}\rangle$

5: Compute a step-size
$\alpha=\operatorname*{\arg\\!\min}_{\alpha\in[0,1]}f(\alpha\mathbf{y}^{t}+(1-\alpha)\mathbf{s})$

6: Move towards the negative conditional gradient
$\mathbf{y}^{t+1}=\alpha\mathbf{y}^{t}+(1-\alpha)\mathbf{s}$

7:end while

Algorithm 1 Frank-Wolfe algorithm

##### Gradient computation

Since the objective function is quadratic, its gradient can be computed as

$\nabla
S_{\text{cvx}}(\mathbf{y})=(\bm{\phi}-\mathbf{d})+2(\bm{\Psi}+\mathbf{D})\mathbf{y}.$
(12)

What makes this equation expensive to compute in a naïve way is the matrix
product with $\bm{\Psi}$. We observe that this operation can be performed
using the filter-based method in linear time. Note that the other matrix-
vector product, $\mathbf{D}\mathbf{y}$, is not expensive (linear in N) since
$\mathbf{D}$ is a diagonal matrix.

##### Conditional gradient

The conditional gradient is obtained by solving

$\operatorname*{\arg\\!\min}_{\mathbf{s}\in\mathcal{M}}\langle\mathbf{s},\nabla
S_{\text{cvx}}(\mathbf{y})\rangle.$ (13)

Minimising such an LP would usually be an expensive operation for problems of
this dimension. However, we remark that, once the gradient has been computed,
exploiting the properties of our problem allows us to solve problem (13) in a
time linear in the number of random variables ($N$) and labels ($M$).
Specifically, the following is an optimal solution to problem (13).

$\mathbf{s}_{a}(i)=\begin{cases}1\quad\text{if
}i=\operatorname*{\arg\\!\min}_{i\in\mathcal{L}}\frac{\partial
S_{\text{cvx}}}{\partial y_{a}(i)}\\\ 0\quad\text{else.}\end{cases}.$ (14)

##### Step size determination

In the original Frank-Wolfe algorithm, the step size $\alpha$ is simply chosen
using line search. However we observe that, in our case, the optimal $\alpha$
can be computed by solving a second-order polynomial function of a single
variable, which has a closed form solution that can be obtained efficiently.
This observation has been previously exploited in the context of Structural
SVM [22]. The derivations for this closed form solution can be found in
Appendix 0.B. With careful reutilisation of computations, this step can be
performed without additional filter-based method calls. By choosing the
optimal step size at each iteration, we reduce the number of iterations needed
to reach convergence.

The above procedure converges to the global minimum of the convex relaxation
and resorts to the filter-based method only once per iteration during the
computation of the gradient and is therefore efficient. However, this solution
has no guarantees to be even a local minimum of the original QP relaxation. To
alleviate this, we will now introduce a difference-of-convex (DC) relaxation.

##  5 Difference of Convex Relaxation

###  5.1 DC relaxation: General case

The objective function of a general DC program can be specified as

$S_{\text{CCCP}}(\mathbf{y})=p(\mathbf{y})-q(\mathbf{y}).$ (15)

One can obtain one of its local minima using the Concave-Convex Procedure
(CCCP) [23]. The key steps of this algorithm are described in Algorithm 2.
Briefly, Step 3 computes the gradient of the concave part. Step 4 minimises a
convex upper bound on the DC objective, which is tight at $\mathbf{y}^{t}$.

In order to exploit the CCCP algorithm for DC programs, we observe that the QP
(8) can be rewritten as

$\begin{split}\min_{\mathbf{y}}\quad&\bm{\phi}^{T}\mathbf{y}+\mathbf{y}^{T}(\bm{\Psi+\mathbf{D}})\mathbf{y}-\mathbf{y}^{T}\mathbf{D}\mathbf{y},\\\
\text{ s.t. }\quad&\mathbf{y}\in\mathcal{M}.\end{split}$ (16)

Formally, we can define
$p(\mathbf{y})=\bm{\phi}^{T}\mathbf{y}+\mathbf{y}^{T}(\bm{\Psi}+\mathbf{D})\mathbf{y}$
and $q(\mathbf{y})=\mathbf{y}^{T}\mathbf{D}\mathbf{y}$, which are both convex
in $\mathbf{y}$.

1:Get $\mathbf{y}^{0}\in\mathcal{M}$

2:while not converged do

3: Linearise the concave part $\mathbf{g}=\nabla q(\mathbf{y}^{t})$

4: Minimise a convex upper-bound
$\mathbf{y}^{t+1}=\operatorname*{\arg\\!\min}_{\mathbf{y}\in\mathcal{M}}p(\mathbf{y})-\mathbf{g}^{T}\mathbf{y}$

5:end while

Algorithm 2 CCCP Algorithm

We observe that, since $\mathbf{D}$ is diagonal and the matrix product with
$\bm{\Psi}$ can be computed using the filter based method, the gradient
$\nabla q(\mathbf{y}^{t})=2\mathbf{D}\mathbf{y}$ (Step 3) is efficient to
compute. The minimisation of the convex problem (Step 4) is analogous to the
convex QP formulation (23) presented above with different unary potentials.
Since we do not place any restrictions on the form of the unary potentials,
(Step 4) can be implemented using the method described in Section 4.

The CCCP algorithm provides a monotonous decrease in the objective function
and will converge to a local minimum [24]. However, the above method will take
several iterations to converge, each necessitating the solution of a convex
QP, and thus requiring multiple calls to the filter-based method. While the
filter-based method [8] allows us to compute operations on the pixel
compatibility function in linear time, it still remains an expensive operation
to perform. As we show next, if we introduce some additional restriction on
our potentials, we can obtain a more efficient difference of convex
decomposition.

###  5.2 DC relaxation: negative semi-definite compatibility

We now introduce a new DC relaxation of our objective function that takes
advantage of the structure of the problem. Specifically, the convex problem to
solve at each iteration does not depend on the filter-based method
computations, which are the expensive steps in the previous method. Following
the example of Krähenbühl and Koltun [10], we look at the specific case of
negative semi-definite label compatibility function, such as the commonly used
Potts model. Taking advantage of the specific form of our pairwise terms (7),
we can rewrite the problem as

$S(\mathbf{y})=\bm{\phi}^{T}\mathbf{y}-\mathbf{y}^{T}(\bm{\mu}\otimes\mathbf{I}_{N})\mathbf{y}^{T}+\mathbf{y}^{T}(\bm{\mu}\otimes\sum_{m}\mathbf{K}^{(m)})\mathbf{y}.$
(17)

The first two terms can be verified as being convex. The Gaussian kernel is
positive semi-definite, so the Gram matrices $\mathbf{K}^{(m)}$ are positive
semi-definite. By assumption, the label compatibility function is also
negative semi-definite. The results from the Kronecker product between the
Gram matrix and $\mathbf{\mu}$ is therefore negative semi-definite.

####  5.2.1 Minimisation.

Once again we use the CCCP Algorithm. The main difference between the generic
DC relaxation and this specific one is that Step 3 now requires a call to the
filter-based method, while the iterations required to solve Step 4 do not. In
other words, each iteration of CCCP only requires one call to the filter based
method. This results in a significant improvement in speed. More details about
this operation are available in Appendix 0.C.

##  6 LP relaxation

This section presents an accurate LP relaxation of the energy minimisation
problem and our method to optimise it efficiently using subgradient descent.

####  6.0.1 Relaxation.

To simplify the description, we focus on the Potts model. However, our
approach can easily be extended to more general pairwise potentials by
approximating them using a hierarchical Potts model. Such an extension,
inspired by [25], is presented in Appendix 0.F. We define the following
notation: $K_{a,b}=\sum_{m}w^{(m)}k^{(m)}(\mathbf{f}^{(m)}_{a}$,
$\mathbf{f}^{(m)}_{b})$, $\sum_{a}=\sum_{a=1}^{N}$ and
$\sum_{b<a}=\sum_{b=1}^{a-1}$. With these notations, a LP relaxation of (5)
is:

$\begin{split}\min\quad&S_{LP}(\mathbf{y})=\underbrace{\sum_{a}\sum_{i}\phi_{a}(i)y_{a}(i)}_{unary}+\underbrace{\sum_{a}\sum_{b\neq
a}\sum_{i}K_{a,b}\frac{|y_{a}(i)-y_{b}(i)|}{2}}_{pairwise},\\\
\text{s.t.}\quad&\mathbf{y}\in\mathcal{M}.\\\ \end{split}$ (18)

The feasible set remains the same as the one we had for the QP and DC
relaxations. In the case of integer solutions, $S_{LP}(\mathbf{y})$ has the
same value as the objective function of the IP described in (5). The $unary$
term is the same for both formulations. The $pairwise$ term ensures that for
every pair of random variables $X_{a},X_{b}$, we add the cost $K_{a,b}$
associated with this edge only if they are not associated with the same
labels.

####  6.0.2 Minimisation.

Kleinberg and Tardos [2] solve this problem by introducing extra variables for
each pair of pixels to get a standard LP, with a linear objective function and
linear constraints. In the case of a dense CRF, this is infeasible because it
would introduce a number of variables quadratic in the number of pixels. We
will instead use projected subgradient descent to solve this LP. To do so, we
will reformulate the objective function, derive the subgradient, and present
an algorithm to compute it efficiently.

##### Reformulation

The absolute value in the pairwise term of (5) prevents us from using the
filtering approach. To address this issue, we consider that for any given
label $i$, the variables $y_{a}(i)$ can be sorted in a descending order:
$a\geq b\implies y_{a}(i)\leq y_{b}(i)$. This allows us to rewrite the
pairwise term of the objective function (18) as:

$\sum_{i}\sum_{a}\sum_{a\neq
b}K_{a,b}\frac{|y_{a}(i)-y_{b}(i)|}{2}=\sum_{i}\sum_{a}\sum_{b>a}K_{a,b}y_{a}(i)-\sum_{i}\sum_{a}\sum_{b<a}K_{a,b}y_{a}(i).$
(19)

A formal derivation of this equality can be found in Appendix 0.D.

##### Subgradient

From (19), we rewrite the subgradient:

$\frac{\partial S_{LP}}{\partial
y_{c}(k)}(\mathbf{y})=\phi_{c}(k)+\sum_{a>c}K_{a,c}-\sum_{a<c}K_{a,c}.\\\ $
(20)

Note that in this expression, the dependency on the variable $\mathbf{y}$ is
hidden in the bounds of the sum because we assumed that $y_{a}(k)\leq
y_{c}(k)$ for all $a>c$. For a different value of $\mathbf{y}$, the elements
of $\mathbf{y}$ would induce a different ordering and the terms involved in
each summation would not be the same.

##### Subgradient computation

What prevents us from evaluating (20) efficiently are the two sums, one over
an upper triangular matrix ($\sum_{a>c}K_{a,c}$) and one over a lower
triangular matrix ($\sum_{a<c}K_{a,c}$). As opposed to (6), which computes
terms $\sum_{a,b}K_{a,b}v_{b}$ for all $a$ using the filter-based method, the
summation bounds here depend on the random variable we are computing the
partial derivative for. While it would seems that the added sparsity provided
by the upper and lower triangular matrices would simplify the operation, it is
this sparsity itself that prevents us from interpreting the summations as
convolution operations. Thus, we cannot use the filter-based method as
described by Adams et al. [8].

We alleviate this difficulty by designing a novel divide-and-conquer
algorithm. We describe our algorithm for the case of the upper triangular
matrix. However, it can easily be adapted to compute the summation
corresponding to the lower triangular matrix. We present the intuition behind
the algorithm using an example. A rigorous development can be found in
Appendix 0.E. If we consider $N=6$ then $a,c\in\\{1,2,3,4,5,6\\}$ and the
terms we need to compute for a given label are:

$\scriptsize\left(\begin{array}[]{c}\sum_{a>1}K_{a,1}\\\ \sum_{a>2}K_{a,2}\\\
\sum_{a>3}K_{a,3}\\\ \sum_{a>4}K_{a,4}\\\ \sum_{a>5}K_{a,5}\\\
\sum_{a>6}K_{a,6}\\\
\end{array}\right)=\underbrace{\left(\begin{array}[]{ccc|ccc}\enskip\text{
}0\text{ }&K_{2,1}&K_{3,1}&K_{4,1}&K_{5,1}&K_{6,1}\\\
0&0&K_{3,2}&K_{4,2}&K_{5,2}&K_{6,2}\\\ 0&0&0&K_{4,3}&K_{5,3}&K_{6,3}\\\
\hline\cr 0&0&0&0&K_{5,4}&K_{6,4}\\\ 0&0&0&0&0&K_{6,5}\\\ 0&0&0&0&0&0\\\
\end{array}\right)}_{\mathbf{U}}\cdot\left(\begin{array}[]{c}1\\\ 1\\\ 1\\\
1\\\ 1\\\ 1\\\ \end{array}\right)$ (21)

We propose a divide and conquer approach that solves this problem by splitting
the upper triangular matrix $\mathbf{U}$. The top-left and bottom-right parts
are upper triangular matrices with half the size. We solve these subproblems
recursively. The top-right part can be computed with the original filter based
method. Using this approach, the total complexity to compute this sum is
$\mathcal{O}(N\log(N))$.

With this algorithm, we have made feasible the computation of the subgradient.
We can therefore perform projected subgradient descent on the LP objective
efficiently. Since we need to compute the subgradient for each label
separately due to the necessity of having sorted elements, the complexity
associated with taking a gradient step is $\mathcal{O}(MN\log(N))$. To ensure
the convergence, we choose as learning rate $(\beta^{t})_{t=1}^{\infty}$ that
is a square summable but not a summable sequence such as
$(\frac{1}{1+t})_{t=1}^{\infty}$. We also make use of the work by Condat [26]
to perform fast projection on the feasible set. The complete procedure can be
found in Algorithm 3. Step 3 to 7 present the subgradient computation for each
label. Using this subgradient, Step 8 shows the update rule for $y^{t}$.
Finally, Step 9 project this new estimate onto the feasible space.

1:Get $\mathbf{y}^{0}\in\mathcal{M}$

2:while not converged do

3: for $i\in\mathcal{L}$ do

4: Sort $y_{a}(i)\quad\forall a\in[1,N]$

5: Reorder $\mathbf{K}$

6: $\mathbf{g}(i)=\nabla S_{LP}(\mathbf{y}^{t}(i))$

7: end for

8: $\mathbf{y}^{t+1}=\mathbf{y}^{t}-\beta^{t}\cdot\mathbf{g}$

9: Project $\mathbf{y}^{t+1}$ on the feasible space

10:end while

Algorithm 3 LP subgradient descent

The algorithm that we introduced converges to a global minimum of the LP
relaxation. By using the rounding procedure introduced by Kleinberg and Tardos
[2], it has a multiplicative bound of 2 for the dense CRF labelling problem on
Potts models and $\mathcal{O}(\log(M))$ for metric pairwise potentials.

##  7 Experiments

We now demonstrate the benefits of using continuous relaxations of the energy
minimisation problem on two applications: stereo matching and semantic
segmentation. We provide results for the following methods: the Convex QP
relaxation ($\mathbf{QP_{cvx}}$), the generic and negative semi-definite
specific DC relaxations ($\mathbf{DC_{gen}}$ and $\mathbf{DC_{neg}}$) and the
LP relaxation (LP). We compare solutions obtained by our methods with the
mean-field baseline (MF).

###  7.1 Stereo matching

####  7.1.1 Data.

We compare these methods on images extracted from the Middlebury stereo
matching dataset [27]. The unary terms are obtained using the absolute
difference matching function of [27]. The pixel compatibility function is
similar to the one used by Krähenbühl and Koltun [5] and is described in
Appendix 0.G. The label compatibility function is a Potts model.

####  7.1.2 Results.

We present a comparison of runtime in Figure (1(a)), as well as the associated
final energies for each method in Table (1(a)). Similar results for other
problem instances can be found in Appendix 0.H.

(a) Runtime comparisons

Method | Final energy
---|---
MF | -1.137e+07
DCneg | -1.145e+07
QP | -1.037e+07
QP-DCneg | -1.191e+07
QP-DCgen | -1.175e+07
QP-DCneg-LP | -1.193e+07
(a) Final Energy achieved

Figure 1: Evolution of achieved energies as a function of time on a stereo
matching problem (Teddy Image). While the QP method leads to the worst result,
using it as an initialisation greatly improves results. In the case of
negative semi-definite potentials, the specific DCneg method is as fast as
mean-field, while additionally providing guarantees of monotonous
decrease.(Best viewed in colour

We observe that continuous relaxations obtain better energies than their mean-
field counterparts. For a very limited time-budget, MF is the fastest method,
although DCneg is competitive and reach lower energies. When using LP,
optimising a better objective function allows us to escape the local minima to
which $\mathbf{DC_{neg}}$ converges. However, due to the higher complexity and
the fact that we need to perform divide-and-conquer separately for all labels,
the method is slower. This is particularly visible for problems with a high
number of labels. This indicates that the LP relaxation might be better suited
to fine-tune accurate solutions obtained by faster alternatives. For example,
this can be achieved by restricting the LP to optimise over a subset of
relevant labels, that is, labels that are present in the solutions provided by
other methods. Qualitative results for the Teddy image can be found in Figure
2 and additional outputs are present in Appendix 0.H. We can see that lower
energy translates to better visual results: note the removal of the artifacts
in otherwise smooth regions (for example, in the middle of the sloped surface
on the left of the image).

Left Image | MF | $\mathbf{DC_{neg}}$ | $\mathbf{QP_{cvx}}$
---|---|---|---
|  |  |
|  |  |
Ground Truth | $\mathbf{QP-DC_{neg}}$ | $\mathbf{QP-DC_{gen}}$ | $\mathbf{QP-DC_{neg}-LP}$

Figure 2: Stereo matching results on the Teddy image. Continuous relaxation
achieve smoother labeling, as expected by their lower energies.

###  7.2 Image Segmentation

####  7.2.1 Data.

We now consider an image segmentation task evaluated on the PASCAL VOC 2010
[28] dataset. For the sake of comparison, we use the same data splits and
unary potentials as the one used by Krähenbühl and Koltun [5]. We perform
cross-validation to select the best parameters of the pixel compatibility
function for each method using Spearmint [29].

####  7.2.2 Results.

The energy results obtained using the parameters cross validated for
$\mathbf{DC_{neg}}$ are given in Table 1. MF5 corresponds to mean-field ran
for 5 iterations as it is often the case in practice [5, 12].

| Unary | MF5 | MF | $\mathbf{QP_{cvx}}$ | $\mathbf{DC_{gen}}$ | $\mathbf{DC_{neg}}$ | LP | Avg. E | Acc | IoU
---|---|---|---|---|---|---|---|---|---|---
Unary | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 79.04 | 27.43
MF5 | 99 | - | 13 | 0 | 0 | 0 | 0 | -600 | 79.13 | 27.53
MF | 99 | 0 | - | 0 | 0 | 0 | 0 | -600 | 79.13 | 27.53
$\mathbf{QP_{cvx}}$ | 99 | 99 | 99 | - | 0 | 0 | 0 | -6014 | 80.38 | 28.56
$\mathbf{DC_{gen}}$ | 99 | 99 | 99 | 85 | - | 0 | 1 | -6429 | 80.41 | 28.59
$\mathbf{DC_{neg}}$ | 99 | 99 | 99 | 98 | 97 | - | 4 | -6613 | 80.43 | 28.60
LP | 99 | 99 | 99 | 98 | 97 | 87 | - | -6697 | 80.49 | 28.68
Table 1: Percentage of images the row method outperforms the column method on
final energy, average energy over the test set and Segmentation performance.
Continuous relaxations dominate mean-field approaches on almost all images and
improve significantly more compared to the Unary baseline. Parameters tuned
for $\mathbf{DC_{neg}}$.

Once again, we observe that continuous relaxations provide lower energies than
mean-field based approaches. To add significance to this result, we also
compare energies image-wise. In all but a few cases, the energies obtained by
the continuous relaxations are better or equal to the mean-field ones. This
provides conclusive evidence for our central hypothesis that continuous
relaxations are better suited to the problem of energy minimisation in dense
CRFs.

For completeness, we also provide energy and segmentation results for the
parameters tuned for MF in Appendix 0.I. Even in that unfavourable setting,
continuous relaxations still provide better energies. Note that, due to time
constraints, we run the LP subgradient descent for only 5 iterations of
subgradient descent. Moreover, to be able to run more experiments, we also
restricted the number of labels by discarding labels that have a very small
probability to appear given the initialisation.

Some qualitative results can be found in Figure 3. When comparing the
segmentations for MF and $\mathbf{DC_{neg}}$, we can see that the best one is
always the one we tune parameters for. A further interesting caveat is that
although we always find a solution with better energy, it does not appear to
be reflected in the quality of the segmentation. While in the previous case
with stereo vision, better energy implied qualitatively better reconstruction
it is not so here. Similar observation was made by Wang et al [20].

Original |  MF Parameters |  $\mathbf{DC_{neg}}$ Parameters
---|---|---
Image | Ground Truth | MF |  $\mathbf{DC_{neg}}$ | MF | $\mathbf{DC_{neg}}$
|  |  |  |  |
|  | E=-3.08367e+7 | E=-3.1012e+7 | E=155992 | E=154100
|  |  |  |  |
|  | E=-3.10922e+7 | E=-3.18649e+7 | E=170968 | E=163308
Figure 3: Segmentation results on sample images. We see that
$\mathbf{DC_{neg}}$ leads to better energy in all cases compared to MF.
Segmentation results are better for MF for the MF-tuned parameters and better
for $\mathbf{DC_{neg}}$ for the $\mathbf{DC_{neg}}$-tuned parameters.

##  8 Discussion

Our main contribution are four efficient algorithms for the dense CRF energy
minimisation problem based on QP, DC and LP relaxations. We showed that
continuous relaxations give better energies than the mean-field based
approaches. Our best performing method, the LP relaxation, suffers from its
high runtime. To go beyond this limit, move making algorithms such as
$\alpha$-expansion [30] could be used and take advantage of the fact that this
relaxation solves exactly the original IP for the two label problem. In future
work, we also want to investigate the effect of learning specific parameters
for these new inference methods using the framework of [18].

## Acknowledgments

This work was supported by the EPSRC, Leverhulme Trust, Clarendon Fund and the
ERC grant ERC-2012-AdG 321162-HELIOS, EPSRC/MURI grant ref EP/N019474/1, EPSRC
grant EP/M013774/1, EPSRC Programme Grant Seebibyte EP/M013774/1 and Microsoft
Research PhD Scolarship Program. We thank Philip Krähenbühl for making his
code available and Vibhav Vineet for his help.

## References

  * [1] Ravikumar, P., Lafferty, J.:  Quadratic programming relaxations for metric labeling and Markov random field MAP estimation.  In: ICML. (2006)
  * [2] Kleinberg, J., Tardos, E.:  Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields.  JACM (2002)
  * [3] Kumar, P., Kolmogorov, V., Torr, P.:  An analysis of convex relaxations for MAP estimation.  In: NIPS.  (2008)
  * [4] Chekuri, C., Khanna, S., Naor, J., Zosin, L.:  Approximation algorithms for the metric labeling problem via a new linear programming formulation.  In: SODA. (2001)
  * [5] Krähenbühl, P., Koltun, V.:  Efficient inference in fully connected CRFs with gaussian edge potentials.  In: NIPS.  (2011)
  * [6] Tappen, M., Liu, C., Adelson, E., Freeman, W.:  Learning gaussian conditional random fields for low-level vision.  In: CVPR. (2007)
  * [7] Koller, D., Friedman, N.:  Probabilistic graphical models: principles and techniques.  (2009)
  * [8] Adams, A., Baek, J., Abraham, M.:  Fast high-dimensional filtering using the permutohedral lattice.  Eurographics (2010)
  * [9] Frank, M., Wolfe, P.:  An algorithm for quadratic programming.  Naval research logistics quarterly (1956)
  * [10] Krähenbühl, P., Koltun, V.:  Parameter learning and convergent inference for dense random fields.  In: ICML. (2013)
  * [11] Baqué, P., Bagautdinov, T., Fleuret, F., Fua, P.:  Principled parallel mean-field inference for discrete random fields.  In: CVPR. (2016)
  * [12] Vineet, V., Warrell, J., Torr, P.:  Filter-based mean-field inference for random fields with higher-order terms and product label-spaces.  IJCV (2014)
  * [13] Ladicky, L., Russell, C., Kohli, P., Torr, P.:  Graph cut based inference with co-occurrence statistics.  In: ECCV.  (2010)
  * [14] Kohli, P., Kumar, P., Torr, P.:  P3 & beyond: Solving energies with higher order cliques.  In: CVPR. (2007)
  * [15] Long, J., Shelhamer, E., Darrell, T.:  Fully convolutional networks for semantic segmentation.  In: CVPR. (2015)
  * [16] Chen, L., Papandreou, G., Kokkinos, I., Murphy, K., Yuille, A.:  Semantic image segmentation with deep convolutional nets and fully connected CRFs.  In: ICLR. (2015)
  * [17] Schwing, A., Urtasun, R.:  Fully connected deep structured networks.  CoRR (2015)
  * [18] Zheng, S., Jayasumana, S., Romera-Paredes, B., Vineet, V., Su, Z., Du, D., Huang, C., Torr, P.:  Conditional random fields as recurrent neural networks.  In: ICCV. (2015)
  * [19] Zhang, Y., Chen, T.:  Efficient inference for fully-connected CRFs with stationarity.  In: CVPR. (2012)
  * [20] Wang, P., Shen, C., van den Hengel, A.:  Efficient SDP inference for fully-connected CRFs based on low-rank decomposition.  In: CVPR. (2015)
  * [21] Goemans, M., Williamson, D.:  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  JACM (1995)
  * [22] Lacoste-Julien, S., Jaggi, M., Schmidt, M., Pletscher, P.:  Block-coordinate frank-wolfe optimization for structural svms.  In: ICML. (2013)
  * [23] Yuille, A., Rangarajan, A.:  The concave-convex procedure (CCCP).  NIPS (2002)
  * [24] Sriperumbudur, B., Lanckriet, G.:  On the convergence of the concave-convex procedure.  In: NIPS. (2009)
  * [25] Kumar, P., Koller, D.:  MAP estimation of semi-metric MRFs via hierarchical graph cuts.  In: UAI. (2009)
  * [26] Condat, L.:  Fast projection onto the simplex and the $l_{1}$ ball.  Mathematical Programming (2015)
  * [27] Scharstein, D., Szeliski, R.:  A taxonomy and evaluation of dense two-frame stereo correspondence algorithms.  IJCV (2002)
  * [28] Everingham, M., Van Gool, L., Williams, C., Winn, J., Zisserman, A.:  The PASCAL Visual Object Classes Challenge 2010 (VOC2010) Results
  * [29] Snoek, J., Larochelle, H., Adams, R.:  Practical bayesian optimization of machine learning algorithms.  In: NIPS. (2012)
  * [30] Boykov, Y., Veksler, O., Zabih, R.:  Fast approximate energy minimization via graph cuts.  PAMI (2001)
  * [31] Bartal, Y.:  On approximating arbitrary metrices by tree metrics.  In: STOC. (1998)
  * [32] Fakcharoenphol, J., Rao, S., Talwar, K.:  A tight bound on approximating arbitrary metrics by tree metrics.  In: STOC. (2003)

##  9 Appendix

##  Appendix 0.A Filter-based method approximation

In this paper, the filter based method that we use for our experiments is the
one by Adams et al. [8]. In this method, the original computation is
approximated by a convolution in a higher dimensional space. The original
points are associated to a set of vertices on which the convolution is
performed. The considered vertices are the one from the permutohedral lattice.
Krähenbühl and Koltun [5] provided an implementation of this method. In their
implementation, they added a pixel-wise normalisation of the output of the
permutohedral lattice and say that it performs well in practice.

We observe that for the variances considered in this paper and without using
the normalisation by Krähenbühl and Koltun, the results given by the
permutohedral lattice is a constant factor away from the value computed by
brute force in most cases. As can be seen in Figure 4, in the case where we
compute $\sum_{a,b}K_{a,b}1$, the left graph, the ratio between the value
obtained by brute force and the value obtained using the permutohedral lattice
is $0.6$ for large enough images. On the other hand, for a different value of
the input points where we compute $\sum_{b>a}K_{a,b}-\sum_{b<a}K_{a,b}$, the
right graph, we get a ratio of $0.48$ between the two results. The case where
we consider a variance of $50$ is special. We know that the highest the
variance value, the worst the approximation of the permutohedral is. If the
experience on the full computation is conducted on an image of size $320\times
213$, the ratio between the brute force approach and the permutohedral lattice
is $0.633$. At the same time is also worth noting that in all these results,
if we consider the outputs as vectors, as is done when computing our
gradients, the vectors given by the brute force and the ones given by the
permutohedral lattice are collinear for all image size and all variances. We
can thus expect that for other input values, the direction of gradient
provided by the permutohedral lattice is correct, but the norm of this vector
may be incorrect.

Full computation | Half computations
---|---
|

Figure 4: Permutohedral lattice approximation. The vertical axis is the value
computed in a brute force manner over the value computed by the permutohedral
lattice. The horizontal axis is the number of pixels in the considered images.
The graph on the left shows this ratio when comparing full permutohedral
lattice computations with only ones as input. The graph on the right shows
this ratio for the divide and conquer approach presented in the LP section. We
can see that in both cases, for sufficiently large images, the permutohedral
lattice computation is a constant factor away from the brute force value. This
constant being a function of the input points values.

##  Appendix 0.B Optimal step size in the Frank-Wolfe algorithm

Solving the convex relaxation of the QP is performed using the Franke-Wolfe
algorithm [9]. The gradient is computed efficiently using the filter-based
method [8]. An efficient method is available to compute the conditional
gradient, based on the gradient. Once this conditional gradient is obtained, a
step size needs to be determined to updates the value of the current
parameters. We show that the optimal step size can be computed and that this
does not introduce any additional call to the filter-based method.

The problem to solve is

$\operatorname*{\arg\\!\min}_{\alpha\in[0,1]}S_{cvx}(\mathbf{y}+\alpha(\mathbf{s}-\mathbf{y})).$
(22)

The definition of $S_{cvx}$ is

$S_{cvx}(\mathbf{y})=(\bm{\phi}-\mathbf{d})^{T}\mathbf{y}+\mathbf{y}^{T}(\bm{\Psi}+\mathbf{D})\mathbf{y}.$
(23)

Solving for the optimal value of $\alpha$ amounts to solving a second order
polynomial:

$\begin{split}S_{cvx}(\mathbf{y}+\alpha(\mathbf{s}-\mathbf{y})&=(\bm{\phi}-\mathbf{d})^{T}(\mathbf{y}+\alpha(\mathbf{s}-\mathbf{y}))\\\
&\qquad+(\mathbf{y}+\alpha(\mathbf{s}-\mathbf{y}))^{T}(\bm{\Psi}+\mathbf{D})(\mathbf{y}+\alpha(\mathbf{s}-\mathbf{y})),\\\
&=\alpha^{2}\left[(\mathbf{s}-\mathbf{y})^{T}(\bm{\Psi}+\mathbf{D})(\mathbf{s}-\mathbf{y})\right]\\\
&\qquad+\alpha\left[(\bm{\phi}-\mathbf{d})^{T}(\mathbf{s}-\mathbf{y})+2\mathbf{y}^{T}(\bm{\Psi}+\mathbf{D})(\mathbf{s}-\mathbf{y})\right]\\\
&\qquad+\quad\left[(\bm{\phi}-\mathbf{d})^{T}\mathbf{y}+\mathbf{y}^{T}(\bm{\Psi}+\mathbf{D})\mathbf{y}\right],\end{split}$
(24)

whose optimal value is given by

$\alpha^{\star}=-\frac{1}{2}\frac{(\bm{\phi}-\mathbf{d})^{T}(\mathbf{s}-\mathbf{y})+2\mathbf{y}^{T}(\bm{\Psi}+\mathbf{D})(\mathbf{s}-\mathbf{y})}{(\mathbf{s}-\mathbf{y})^{T}(\bm{\Psi}+\mathbf{D})(\mathbf{s}-\mathbf{y})}$
(25)

The dot products are going to be linear in complexity and efficient. Using the
filtering approach, the matrix-vector operation are also linear in complexity.
In terms of run-time, they represent the costliest step so minimising the
number of times that we are going to perform them will gives us the best
performance for our algorithm. We remind the reader that the expression of the
gradient used at an iteration is:

$\nabla
S_{\text{cvx}}(\mathbf{y})=(\bm{\phi}-\mathbf{d})+2(\bm{\Psi}+\mathbf{D})\mathbf{y}.$
(26)

so by keeping intermediary results of the gradient’s computation, we don’t
need to compute $(\bm{\Psi}+\mathbf{D})\mathbf{y}$, having already performed
this operation once. The other matrix-vector product that is necessary for
obtaining the optimal step-size is $(\bm{\Psi}+\mathbf{D})\mathbf{s}$. During
the first iteration, we will need to compute is using filter-based methods,
which means using them twice in the same iteration. However, this computation
can be reused. The update rules that we follow are:

$\mathbf{y}^{t+1}=\mathbf{y}^{t}+\alpha(\mathbf{s}-\mathbf{y}^{t}).$ (27)

At the following iteration, to obtain the gradient, we will need to compute:

$\begin{split}(\bm{\Psi}+\mathbf{D})\mathbf{y}^{t+1}&=(\bm{\Psi}+\mathbf{D})(\mathbf{y}^{t}+\alpha(\mathbf{s}-\mathbf{y}^{t}),\\\
&=(1-\alpha)(\bm{\Psi}+\mathbf{D})\mathbf{y}^{t}+\alpha(\bm{\Psi}+\mathbf{D})\mathbf{s}.\end{split}$
(28)

All the matrix-vector product of this equation have already been computed.
This means that no call to the filter-based method will be required.

At each iteration, we will only need to perform the expensive matrix-vector
products on the conditional gradient. Using linearity and keeping track of our
previous computations, we can then obtain all the other terms that we need.

##  Appendix 0.C Convex problem in the restricted DC relaxation

Two difference-of-convex decompositions of the objective function are
presented in the paper. The first one is based on diagonally dominant matrices
to ensure convexity and would be applicable to any QP objective function.
However, using this decomposition, the terms involving the pixel-compatibility
function, and therefore requiring filter-based convolutions, need to be
computed several times per CCCP iteration.

On the other hand, in the case of negative semi-definite compatibility
functions, a decomposition suited to the structure of the problem is
available. Using this decomposition, similar to the one proposed by Krähenbühl
[10], the convex problem to solve CCCP will be the following:

$\begin{split}\min&\quad(\bm{\phi}^{T}-\mathbf{g}^{T})\mathbf{y}-\mathbf{y}^{T}(\bm{\mu}\otimes\mathbf{I}_{N})\mathbf{y},\\\
\text{s.t. }&\quad\mathbf{y}\in\mathcal{M}.\end{split}$ (29)

The filter-method has been used to compute the gradient of the concave part
$\mathbf{g}$. The Kronecker product with the identity matrix will make this
problem completely de-correlated between pixels. This means that instead of
solving one problem involving $N\times L$ variables, we will have to solve $N$
problems of $L$ variables, which is much faster. The problem to solve for each
pixel are, using the $a$ subscript to refer to the subset of the vector
elements that correspond to the random variable $a$:

$\begin{split}\min&\quad(\bm{\phi}_{a}^{T}-\mathbf{g}_{a}^{T})\mathbf{y}_{a}-\mathbf{y}_{a}^{T}\bm{\mu}\mathbf{y}_{a},\\\
\text{s.t. }&\quad\mathbf{y}_{a}\geq 0\\\
&\quad\mathbf{y}_{a}^{T}\mathds{1}=1.\end{split}$ (30)

These problems can also be solved using the Frank-Wolfe algorithm, with
efficient conditional gradient computation and optimal step size. The only
difference is that in that case, no filter-based method will need to be used
for computation. CCCP on this DC relaxation will therefore be much faster than
on the generic case, an improvement gained at the cost of generality.

We also remark that the guarantees of CCCP to provide better results at each
iteration does not require to solve the convex problem exactly. It is
sufficient to obtain a value of the convex problem lower that the initial
estimate. Therefore, the inference may eventually be sped-up by solving the
convex problem approximately instead of reaching the optimal solution.

##  Appendix 0.D LP objective reformulation

This section presents the reformulation of the pairwise part of the LP
objective. We first introduce the following equality:

$\sum_{a}\sum_{b>a}K_{a,b}y_{b}(i)=\sum_{a}\sum_{b<a}K_{a,b}y_{a}(i),$ (31)

It comes from the symmetry of $\mathbf{K}$.

Using the above formula, considering the reordering has already been done, we
can rewrite the pairwise term of (18) as:

$\begin{split}&\sum_{a}\sum_{b\neq
a}\sum_{i}K_{a,b}\frac{|y_{a}(i)-y_{b}(j)|}{2},\\\
=&\sum_{i}\sum_{a}\sum_{b>a}K_{a,b}\frac{y_{a}(i)-y_{b}(i)}{2}-\sum_{i}\sum_{a}\sum_{b<a}K_{a,b}\frac{y_{a}(i)-y_{b}(i)}{2},\\\
=&\sum_{i}\sum_{a}\sum_{b>a}K_{a,b}y_{a}(i)-\sum_{i}\sum_{a}\sum_{b<a}K_{a,b}y_{a}(i).\end{split}$
(32)

It is important to note that in these equations, the ordering between $a$ and
$b$ used in the summations is dependent on the considered label $i$.

##  Appendix 0.E LP Divide and conquer

We are going to present an algorithm to efficiently compute the following:

$\forall k\quad\sum_{j>k}K_{k,j},$ (33)

for $j$ and $k$ being between $1$ and $N$. For the sake of simplicity, we are
going to consider $N$ as being even. The odd case is very similar. Considering
$h=N/2$, we can rewrite the original sum as:

$\begin{split}\sum_{j>k}K_{k,j}=&\begin{cases}\hfill\sum_{j>k}K_{k,j}\hfill&\text{
if }k>h\\\ \hfill\sum_{j>k}K_{k,j}\hfill&\text{ if }k\leq h\\\ \end{cases}\\\
=&\begin{cases}\hfill\sum_{j>k}K_{k,j}\hfill&\text{ if }k>h\\\
\hfill\sum_{\begin{subarray}{c}j>k\\\ j\leq
h\end{subarray}}K_{k,j}+\sum_{\begin{subarray}{c}j>k\\\
j>h\end{subarray}}K_{k,j}\hfill&\text{ if }k\leq h\\\ \end{cases}\\\
=&\begin{cases}\hfill\underbrace{\sum_{j>k}K_{k,j}}_{A}\hfill&\text{ if
}k>h\\\ \hfill\underbrace{\sum_{\begin{subarray}{c}j>k\\\ j\leq
h\end{subarray}}K_{k,j}}_{B}+\underbrace{\sum_{\begin{subarray}{c}j>h\end{subarray}}K_{k,j}}_{C}\hfill&\text{
if }k\leq h\\\ \end{cases}\\\ \end{split}$ (34)

We can see that both $A$ and $B$ corresponds to the cases where respectively
$k,j>h$ and $k,j\leq h$. These two elements can be obtained by recursion using
sub-matrices of $\mathbf{K}$ which have half the size of the current size of
the problem. To compute the $C$ part, we consider the following variable:

$v_{j}=\begin{cases}\hfill 0\hfill&\text{ if }j\leq h\\\ \hfill 1\hfill&\text{
if }j>h\\\ \end{cases}$ (35)

We can now rewrite the $C$ part as
$\sum_{\begin{subarray}{c}j\end{subarray}}K_{k,j}v_{j}$. We can compute this
sum efficiently for all $k$ using the filter-based method. Since this term
contribute to the original sum only when $k\leq h$, we will only consider a
subset of the output from the filter based method.

So we have a recursive algorithm that will have a depth of $log(N)$ and for
which all level takes $\mathcal{O}(N)$ to compute. We can use it to compute
the requested sum $\forall k$ in $\mathcal{O}(Nlog(N))$.

##  Appendix 0.F LP generalisation beyond Potts models

In this section, we consider the case where the label compatibility
$\mu(x_{a},x_{b})$ is any semi-metric. We recall that $\mu(\cdot,\cdot)$ is a
semi-metric if and only if $d(i,i)=0,\forall i$ and $d(i,j)=d(j,i)>0,\forall
i\neq j$.

To solve this problem, we are going to reduce the semi-metric labelling
problem to a r-hierarchically well-separated tree (r-HST) labelling problem
that we can then reduce to a uniform labelling problem.

As described in [25], an r-HST metric [31] $d^{t}(\cdot,\cdot)$ is specified
by a rooted tree whose edge lengths are non-negative and satisfy the following
properties: (i) the edge lengths from any node to all of its children are the
same; and (ii) the edge lengths along any path from the root to a leaf
decrease by a factor of at least $r>1$. Given such a tree, known as r-HST, the
distance $d^{t}(i,j)$ is the sum of the edge lengths on the unique path
between them

###  0.F.1 Approximate the semi-metric with r-HST metric

Fakcharoenphol et al. [32] present an algorithm to get in polynomial time a
mixture of r-HST that approximate any semi-metric using a fixed number of
trees. This algorithm generate a collection
$\mathcal{D}={d^{t}(\cdot,\cdot),t=1,...,n}$ where each $d^{t}$ is a r-HST
metric.

Since this mixture of r-HST metric is an approximation to the original metric,
we can approximate the original labelling problem by solving the labelling
problem on each of these r-HST metrics and combining them with the method
presented in [25]. We are now going to present an efficient algorithm to solve
the problem on an r-HST. This algorithm can then be used to solve the problem
in the semi-metric case.

###  0.F.2 Solve the r-HST labelling problem

We now consider a given r-HST metric $d^{t}$ and we note $\mathcal{T}$ all the
sub-trees corresponding to this metric and we will use $T$ as one of these
sub-trees. This problem has been formulated by Kleinberg and Tardos [2], but
we are not using their method to solve it because the density of our CRF makes
their method unfeasible. We are going to solve their original LP directly:

$\begin{split}\min\quad&\sum_{a}\sum_{i}\phi_{a}(i)y_{a}(i)+\sum_{a,b\neq
a}\sum_{T}K_{a,b}c_{T}\frac{|y_{a}(T)-y_{b}(T)|}{2}\\\ \text{such
that}\quad&\sum_{i}y_{a}(i)=1\quad\forall a\\\ &y_{a}(T)=\sum_{i\in
L(T)}y_{a}(i)\quad\forall a\forall T\\\ &y_{a}(i)\in\\{0,1\\}\quad\forall
a,i\\\ \end{split}$ (36)

Where $L(T)$ is the set of all labels associated with a sub-tree $T$.

This problem is the same the Potts model case except for two points:

  * •

In the pairwise term, the labels have been replaced by sub-trees. Since the
assignment of the labels to the trees does not change, this won’t prevent us
from using the same method to compute the gradient.

  * •

There is a factor $c_{T}$ corresponding to the weights in the tree. This does
not prevents us from computing this efficiently since we can move this out of
the inner loop with the summation over the trees.

Using the same trick where we sort the $y_{a}(T)$ for all $T$, we can rewrite
the pairwise part of the above problem and compute its sub-gradient. Using the
fact that $\frac{\partial y_{a}(T)}{\partial y_{c}(k)}$ is $0$ if $a\neq c$ or
$k\not\in L(T)$ and $1$ otherwise and noting $T_{k}$ all the sub-trees that
contains $k$ as one of their label.

$\begin{split}&\frac{\partial}{\partial y_{c,k}}(\sum_{T}\sum_{a,b\neq
a}K_{a,b}c_{T}\frac{|y_{a}(T)-y_{b}(T)|}{2})\\\ =&\frac{\partial}{\partial
y_{c,k}}(\sum_{T}\sum_{a,b}K_{a,b}c_{T}\frac{y_{a}(T)-y_{b}(T)}{2})-2\sum_{T}\sum_{a,b<a}K_{a,b}c_{T}\frac{y_{a}(T)-y_{b}(T)}{2})\\\
=&\sum_{T_{k}}\sum_{b}c_{T_{k}}\frac{K_{c,b}}{2}-\sum_{T_{k}}\sum_{a}c_{T_{k}}\frac{K_{a,c}}{2}-2\sum_{T_{k}}\sum_{b<c}c_{T_{k}}\frac{K_{c,b}}{2}+2\sum_{T_{k}}\sum_{a>c}c_{T_{k}}\frac{K_{a,c}}{2}\\\
=&-\sum_{T_{k}}\sum_{a<c}c_{T_{k}}K_{a,c}+\sum_{T_{k}}\sum_{a>c}c_{T_{k}}K_{a,c}\\\
=&\sum_{T_{k}}c_{T_{k}}(\sum_{a>c}K_{a,c}-\sum_{a<c}K_{a,c})\end{split}$ (37)

Since the sorting is done for each sub-tree $T$, the sums where we consider
relative ordering of the indices cannot be switched and thus we cannot
simplify this expression further.

We present a method to solve this problem in Algorithm 4. State 3 initialise
the subgradient with the unaries. The loop at State 4 is used to compute the
participation of each subtree to the total subgradient. To do so, we first
precompute the $y_{a}(T)$ terms for all pixel in the loop starting at State 5.
We then sort these $y_{a}(T)$ in State 8 and reorder the $\mathbf{K}$ matrix
accordingly in State 9. Using this, we can use the divide and conquer approach
from the Potts model section to compute the participation of this tree to the
subgradient for each pixel using the formula from State 10. The vector
$\mathbf{gt}$ is of size $N$ and contains one value per pixel. We can now
update the subgradient with the partial one on this tree for all labels
associated with this tree. The notation $\mathbf{g_{\cdot,k}}$ corresponds to
a single row of the gradient matrix. This is done in the for loop starting at
State 11. We can perform one step of subgradient descent in State 17. Finally
we need to project the new point on the feasible set at State 18

1:Get $\mathbf{y}^{0}$

2:while not converged do

3: Initialise the subgradient $\mathbf{g}=\bm{\phi}$

4: for all subtree $T$ do

5: for all pixel $a$ do

6: $y_{a}(T)=\sum_{i\in L(T)}y_{a}(i)$

7: end for

8: Sort $y_{a}(T)$

9: Reorder $\mathbf{K}$

10: Gradient for this subtree
$gt_{c}=c_{T}(\sum_{a>c}K_{a,c}-\sum_{a<c}K_{a,c})$

11: for all label $k$ do

12: if $k\in T$ then

13: Update $\mathbf{g_{\cdot,k}}\mathrel{+}=\mathbf{gt}$

14: end if

15: end for

16: end for

17: $\mathbf{y}^{t+1}=\mathbf{y}^{t}-\beta\mathbf{g}$

18: Project $\mathbf{y}^{t+1}$ such that it is a feasible point

19:end while

Algorithm 4 r-HST labelling problem

##  Appendix 0.G Model used in the experiments section

All the results that we presented in the paper are valid for pixel
compatibility functions composed of a mixture of Gaussian kernels:

$\sum_{m}w^{(m)}k(\mathbf{f}^{(m)}_{a},\mathbf{f}^{(m)}_{b}).$ (38)

In practice, for our experiments, we use the same form as Krähenbühl and
Koltun [5]. It is a mixture of two gaussian kernels defined using the position
vectors $\mathbf{p}_{a}$ and $\mathbf{p}_{b}$, and the colour vectors
$\mathbf{I}_{a}$ and $\mathbf{I}_{b}$ associated with each pixel $a$ and $b$.
The complete formula is the following:

$K_{a,b}=w^{(1)}\exp\left(-\frac{|\mathbf{p}_{a}-\mathbf{p}_{b}|^{2}}{\sigma_{1}}\right)+w^{(2)}\exp\left(-\frac{|\mathbf{p}_{a}-\mathbf{p}_{b}|^{2}}{\sigma_{2,\text{spc}}}-\frac{\mathbf{|\mathbf{I}_{a}-\mathbf{I}_{b}|^{2}}}{\sigma_{2,\text{col}}}\right).$
(39)

We note that this pixel compatibility function contains 5 learnable parameters
$w^{(1)},\sigma_{1},w^{(2)},\sigma_{2,\text{spc}},\sigma_{2,\text{col}}$.

##  Appendix 0.H More results on stereo

In the following Figures 8, 10 and 9, we observe that the continuous
relaxations give consistently better results. We can also note that even
though it runs only for a few iterations, the LP improves the visual quality
of the solution.

Method | Final energy
---|---
MF | -1.341e+07
DCneg | -1.344e+07
QP | -1.341e+07
QP-DCneg | -1.354e+07
QP-DCgen | -1.352e+07
QP-DCneg-LP | -1.354e+07
Figure 5: Evolution of achieved energies as a function of time on a stereo matching problem (Venus Image). Method | Final energy
---|---
MF | -9.286e+06
DCneg | -9.388e+06
QP | -8.881e+06
QP-DCneg | -9.868e+06
QP-DCgen | -9.757e+06
QP-DCneg-LP | -9.758e+06
Figure 6: Evolution of achieved energies as a function of time on a stereo matching problem (Cones Image). Note that the LP in that case is not improving the results. Method | Final energy
---|---
MF | -8.927e+06
DCneg | -8.920e+06
QP | -9.101e+06
QP-DCneg | -9.215e+06
QP-DCgen | -9.177e+06
QP-DCneg-LP | -9.186e+06
Figure 7: Evolution of achieved energies as a function of time on a stereo
matching problem (Tsukuba Image). Note that the LP in that case is not
improving the results.

Left Image | MF | $\mathbf{DC_{neg}}$ | $\mathbf{QP_{cvx}}$
---|---|---|---
|  |  |
|  |  |
Ground Truth | $\mathbf{QP-DC_{neg}}$ | $\mathbf{QP-DC_{neg}}$ | $\mathbf{QP-DC_{neg}-LP}$

Figure 8: Stereo matching results on the Tsukuba image and corresponding
timings. We see that the LP method allows to improve the smoothness from its
initialisation $\mathbf{DC_{neg}}$. For this set of parameters, the mean-field
methods performs poorly.

Left Image | MF | $\mathbf{DC_{neg}}$ | $\mathbf{QP_{cvx}}$
---|---|---|---
|  |  |
|  |  |
Ground Truth | $\mathbf{QP-DC_{neg}}$ | $\mathbf{QP-DC_{neg}}$ | $\mathbf{QP-DC_{neg}-LP}$

Figure 9: Stereo matching results on the Cones image and corresponding
timings. Here again, we can see that the MF solution is significantly better
than the MF5 solution. The continuous relaxations improve even further by
reducing the number of artifacts.

Left Image | MF | $\mathbf{DC_{neg}}$ | $\mathbf{QP_{cvx}}$
---|---|---|---
|  |  |
|  |  |
Ground Truth | $\mathbf{QP-DC_{neg}}$ | $\mathbf{QP-DC_{neg}}$ | $\mathbf{QP-DC_{neg}-LP}$

Figure 10: Stereo matching results on the Venus image. Note that the
smoothness of the reconstructions improves with methods reaching lower
energies. The LP result does not artefacts anymore, only the non contiguous
borders due to the Potts model.

##  Appendix 0.I More results on segmentation

Additional results for parameters cross-validated for MF are presented in
Table 4.

We see that in this case where the parameters are tuned for MF, the continuous
relaxations still reach lower energy than the mean-field approaches on
average. Furthermore, we observe that in almost all images, the energy is
strictly lower than the one provided by the mean-field methods. However, with
the parameters that were tuned for MF using cross-validation, we note that the
segmentation performance is poor compared to mean-field approaches, and that
the improved energy minimisation does not translate to better segmentation.

| Unary | MF5 | MF | $\mathbf{QP_{cvx}}$ | $\mathbf{DC_{gen}}$ | $\mathbf{DC_{neg}}$ | LP | Avg. E | Acc | IoU
---|---|---|---|---|---|---|---|---|---|---
Unary | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 79.04 | 27.43
MF5 | 99 | - | 0 | 1 | 0 | 1 | 1 | -8.37e5 | 80.42 | 28.66
MF | 99 | 93 | - | 4 | 2 | 3 | 3 | -1.19e6 | 80.95 | 28.86
$\mathbf{QP_{cvx}}$ | 99 | 93 | 86 | - | 0 | 4 | 2 | -1.66e6 | 77.75 | 14.94
$\mathbf{DC_{gen}}$ | 99 | 94 | 88 | 32 | - | 29 | 29 | -1.68e6 | 77.76 | 14.96
$\mathbf{DC_{neg}}$ | 99 | 93 | 87 | 27 | 2 | - | 12 | -1.67e6 | 77.76 | 14.91
LP | 99 | 93 | 87 | 29 | 2 | 17 | - | -1.67e6 | 77.77 | 14.93
Table 4: Percentage of images obtaining strictly lower energy values. Average
energy results over the test set and Segmentation performance. Higher
percentage is better and lower energy is better. Higher accuracy and IoU are
better. Continuous relaxations dominate mean-field approaches on almost all
images and improve significantly more compared to the Unary baseline.
Parameters tuned for MF.


the usage of network components other than linear layers, or the incorporation
of the clustering performance on the code space into the loss function.
Additionally, we did not account for the information loss caused by encoding
high-dimensional data into a two-dimensional embedded space.

In future work, it is important to use not only AMI to evaluate the clustering
algorithm, but to also consider metrics such as absolute size of overlap of
the original and generated data clustering and average and variance of the
cluster sizes in the algorithm output. We also plan to expand our evaluation
in two directions: adding more data quality dimensions and conducting a deeper
evaluation per ML-model.

###### Acknowledgements.

This research was performed in the context of the KITQAR project, supported by
Denkfabrik Digitale Arbeitsgemeinschaft im Bundesministerium für Arbeit und
Soziales (BMAS).

## References

  * (1) Aditya  “100,000 UK Used Car Data Set” https://www.kaggle.com/adityadesai13/used-car-dataset-ford-and-mercedes/version/3, visited 2022-03-11
  * (2) Aleryani, Wenjia Wang and Beatriz Iglesia  “Multiple Imputation Ensembles (MIE) for Dealing with Missing Data”  In _SN Computer Science_ 1.3 Springer, 2020, pp. 1–20
  * (3) Naomi S Altman  “An introduction to kernel and nearest-neighbor nonparametric regression”  In _The American Statistician_ 46.3 Taylor & Francis Group, 1992, pp. 175–185
  * (4) M. Ankerst, M. M. Breunig, H.-P. Kriegel and J. Sander  “OPTICS: Ordering Points to Identify the Clustering Structure”  In _SIGMOD Record_ 28.2, 1999, pp. 49–60
  * (5) Carlo Batini and Monica Scannapieco  “Data Quality: Concepts, Methods and Techniques”  Berlin – Heidelberg – New York: Springer Verlag, 2006
  * (6) Felix Biessmann et al.  “Automated Data Validation in Machine Learning Systems”  In _IEEE Data Engineering Bulletin_ 44.1, 2021, pp. 51–65
  * (7) J. A. Blackard  “Covertype Data Set” https://archive.ics.uci.edu/ml/datasets/Covertype, visited 2022-03-11
  * (8) J. A. Blackard and D. J. Dean  “Comparative Accuracies of Artificial Neural Networks and Discriminant Analysis in Predicting Forest Cover Types from Cartographic Variables”  In _Computers and Electronics in Agriculture_ 24.3 Elsevier, 1999, pp. 131–151
  * (9) Eric Breck et al.  “Data Validation for Machine Learning”  In _Proceedings of Machine Learning and Systems 2019, MLSys 2019_ Stanford, CA, USA: mlsys.org, 2019
  * (10) L. Breiman  “Random forests”  In _Machine Learning_ 45.1 Springer, 2001, pp. 5–32
  * (11) Leo Breiman, J. H. Friedman, R. A. Olshen and C. J. Stone  “Classification and Regression Trees”  Wadsworth, 1984
  * (12) G. Chen, J. Vandenbulcke and E. E. Kerre  “A General Treatment of Data Redundancy in a Fuzzy Relational Data Model”  In _Journal of the American Society for Information Science_ 43.4, 1992, pp. 304–311  URL: https://asistdl.onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-4571%28199205%2943%3A4%3C304%3A%3AAID-ASI6%3E3.0.CO%3B2-X
  * (13) P. Christen and K. Goiser  “Quality and Complexity Measures for Data Linkage and Deduplication”  In _Quality Measures in Data Mining_ Springer, 2007, pp. 127–151
  * (14) D. De Cock  “Ames, Iowa: Alternative to the Boston Housing Data as an End of Semester Regression Project”  In _Journal of Statistics Education_ 19.3 Taylor & Francis, 2011, pp. null  DOI: 10.1080/10691898.2011.11889627
  * (15) NVIDIA Corporation  “CUDA Toolkit” https://developer.nvidia.com/cuda-toolkit, visited 2022-03-11
  * (16) Corinna Cortes and Vladimir Vapnik  “Support-vector networks”  In _Machine learning_ 20.3 Springer, 1995, pp. 273–297
  * (17) W. H. E. Day and H. Edelsbrunner  “Efficient Algorithms for Agglomerative Hierarchical Clustering Methods”  In _Journal of Classification_ 1.1 Springer, 1984, pp. 7–24
  * (18) Developers  “OPTICS” https://scikit-learn.org/stable/modules/generated/sklearn.cluster.OPTICS.html, visited 2022-03-11
  * (19) D. Dua and C. Graff  “UCI Machine Learning Repository” http://archive.ics.uci.edu/ml, visited 2022-03-11, 2017
  * (20) Martin Ester, Hans-Peter Kriegel, Jörg Sander and Xiaowei Xu  “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”  In _Proceedings of the International Conference on Knowledge discovery and data mining (SIGKDD)_ AAAI Press, 1996, pp. 226–231
  * (21) Inc. Facebook  “PyTorch: From Research to Production”, https://pytorch.org/
  * (22) Matthias Feurer et al.  “Efficient and Robust Automated Machine Learning”  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2015, pp. 2962–2970
  * (23) Daniele Foroni, Matteo Lissandrini and Yannis Velegrakis  “Estimating the extent of the effects of Data Quality through Observations”  In _Proceedings of the International Conference on Data Engineering (ICDE)_ , 2021, pp. 1913–1918  DOI: 10.1109/ICDE51399.2021.00176
  * (24) Benoît Frénay and Michel Verleysen  “Classification in the Presence of Label Noise: A Survey”  In _IEEE Trans. Neural Networks Learn. Syst._ 25.5, 2014, pp. 845–869  DOI: 10.1109/TNNLS.2013.2292894
  * (25) Timnit Gebru et al.  “Datasheets for datasets”  In _Communications of the ACM_ 64.12, 2021, pp. 86–92  DOI: 10.1145/3458723
  * (26) J. C. Gower  “A General Coefficient of Similarity and Some of its Properties”  In _Biometrics_ 27.04 JSTOR, 1971, pp. 857–871
  * (27) Christoph Gröger  “There is No AI without Data”  In _Communications of the ACM_ 64.11 New York, NY, USA: Association for Computing Machinery, 2021, pp. 98–108  DOI: 10.1145/3448247
  * (28) U. Grömping  “South German Credit Data: Correcting a Widely Used Data Set”, 2019  URL: http://www1.beuth-hochschule.de/FB_II/reports/Report-2019-004.pdf
  * (29) Venkat Gudivada, Amy Apon and Junhua Ding  “Data quality considerations for big data and machine learning: Going beyond data cleaning and transformations”  In _International Journal on Advances in Software_ 10.1, 2017, pp. 1–20
  * (30) Nitin Gupta et al.  “Data Quality Toolkit: Automatic assessment of data quality and remediation for machine learning datasets”  In _CoRR_ abs/2108.05935, 2021  arXiv: https://arxiv.org/abs/2108.05935
  * (31) D. Harrison and D. L. Rubinfeld  “Hedonic Housing Prices and the Demand for Clean Air”  In _Journal of Environmental Economics and Management_ 5.1, 1978, pp. 81–102  DOI: https://doi.org/10.1016/0095-0696(78)90006-2
  * (32) A. E. Hoerl and R. W. Kennard  “Ridge Regression: Biased Estimation for Nonorthogonal Problems”  In _Technometrics_ 12.1 Taylor & Francis, 1970, pp. 55–67
  * (33) Prof. H. Hofmann  “Creditworthiness Dataset” https://archive.ics.uci.edu/ml/datasets/statlog+(german+credit+data), visited 2022-03-11
  * (34) IBM  “Telco Customer Churn Dataset” https://www.kaggle.com/blastchar/telco-customer-churn, visited 2022-03-11
  * (35) I. F. Ilyas and X. Chu  “Trends in Cleaning Relational Data: Consistency and Deduplication”  In _Foundations and Trends in Databases_ 5.4 Now Publishers Inc. Hanover, MA, USA, 2015, pp. 281–393
  * (36) J. Ji et al.  “An Improved k-Prototypes Clustering Algorithm for Mixed Numeric and Categorical Data”  In _Neurocomputing_ 120 Elsevier, 2013, pp. 590–596
  * (37) Kaggle  “House Prices - Advanced Regression Techniques” https://www.kaggle.com/c/house-prices-advanced-regression-techniques, visited 2022-03-11
  * (38) Diederik P. Kingma and Jimmy Ba  “Adam: A Method for Stochastic Optimization”  In _International Conference on Learning Representations (ICLR)_ , 2015
  * (39) Ch. N. S. Kumar, K. N. Rao, A. Govardhan and N. Sandhya  “Subset k-Means Approach for Handling Imbalanced-distributed Data”  In _Emerging ICT for Bridging the Future-Proceedings of the Annual Convention of the Computer Society of India CSI Volume 2_ Springer, 2015, pp. 497–508
  * (40) M. Last, O. Maimon and E. Minkov  “Improving Stability of Decision Trees”  In _International Journal of Pattern Recognition and Artificial Intelligence_ 16.02 World Scientific, 2002, pp. 145–159
  * (41) Colin Lewis-Beck and Michael Lewis-Beck  “Applied regression: An introduction”  Sage publications, 2015
  * (42) Peng Li et al.  “CleanML: A Study for Evaluating the Impact of Data Cleaning on ML Classification Tasks”  In _Proceedings of the International Conference on Data Engineering (ICDE)_ , 2021, pp. 13–24  URL: https://doi.org/10.1109/ICDE51399.2021.00009
  * (43) T.-S. Lim  “Contraceptive Method Choice Data Set”, 1987
  * (44) R. J. A. Little and D. B. Rubin  “Statistical Analysis with Missing Data”  Wiley, 2014  DOI: 10.1002/9781119013563
  * (45) S. Lu and R. Li  “DAC–Deep Autoencoder-Based Clustering: A General Deep Learning Framework of Representation Learning”  In _Proceedings of SAI Intelligent Systems Conference_ Virtual Event: Springer, 2021, pp. 205–216
  * (46) Peter McCullagh and John A. Nelder  “Generalized Linear Models”  Springer, 1989  DOI: 10.1007/978-1-4899-3242-6
  * (47) D. C. Montgomery, E. A. Peck and G. G. Vining  “Introduction to Linear Regression Analysis”  John Wiley & Sons, 2021
  * (48) S. Moro, P. Cortez and P. Rita  “A Data-driven Approach to Predict the Success of Bank Telemarketing”  In _Decision Support Systems_ 62 Elsevier, 2014, pp. 22–31
  * (49) Felix Neutatz et al.  “Data Cleaning and AutoML: Would an Optimizer Choose to Clean?”  In _Datenbank Spektrum_ 22.2, 2022, pp. 121–130  DOI: 10.1007/s13222-022-00413-2
  * (50) Felix Neutatz, Binger Chen, Ziawasch Abedjan and Eugene Wu  “From Cleaning before ML to Cleaning for ML”  In _IEEE Data Eng. Bull._ 44.1, 2021, pp. 24–41  URL: http://sites.computer.org/debull/A21mar/p24.pdf
  * (51) Xuan Vinh Nguyen, Julien Epps and James Bailey  “Information theoretic measures for clusterings comparison: is a correction for chance necessary?”  In _Proceedings of the International Conference on Machine Learning (ICML)_ 382, ACM International Conference Proceeding Series  ACM, 2009, pp. 1073–1080  DOI: 10.1145/1553374.1553511
  * (52) Curtis G. Northcutt, Anish Athalye and Jonas Mueller  “Pervasive Label Errors in Test Sets Destabilize Machine Learning Benchmarks”  In _Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks_ , 2021  URL: https://datasets-benchmarks-proceedings.neurips.cc/paper/2021/hash/f2217062e9a397a1dca429e7d70bc6ca-Abstract-round1.html
  * (53) F. Pedregosa et al.  “Scikit-learn: Machine Learning in Python”  In _Journal of Machine Learning Research_ 12, 2011, pp. 2825–2830
  * (54) Neoklis Polyzotis, Sudip Roy, Steven Euijong Whang and Martin Zinkevich  “Data Lifecycle Challenges in Production Machine Learning: A Survey”  In _SIGMOD Record_ 47.2, 2018, pp. 17–28  DOI: 10.1145/3299887.3299891
  * (55) M. Ramadan  “IMDb Most Popular Films and Series” https://www.kaggle.com/mazenramadan/imdb-most-popular-films-and-series/version/3, visited 2022-03-11
  * (56) Cédric Renggli et al.  “A Data Quality-Driven View of MLOps”  In _IEEE Data Engineering Bulletin_ 44.1, 2021, pp. 11–23  URL: http://sites.computer.org/debull/A21mar/p11.pdf
  * (57) D. A. Reynolds  “Gaussian Mixture Models”  In _Encyclopedia of Biometrics_ 741 Berlin, Springer, 2009, pp. 827–832
  * (58) Lior Rokach and Oded Maimon  “Clustering Methods”  In _The Data Mining and Knowledge Discovery Handbook_ Springer, 2005, pp. 321–352
  * (59) Chris Ré  “The Road to Software 2.0 or Data‑Centric AI”, 2021  URL: https://hazyresearch.stanford.edu/data-centric-ai
  * (60) P. Cortez S. Moro and P. Rita  “Bank Marketing Data Set” https://archive.ics.uci.edu/ml/datasets/bank+marketing, visited 2022-03-11
  * (61) Sebastian Schelter, Tammo Rukat and Felix Biessmann  “JENGA - A Framework to Study the Impact of Data Errors on the Predictions of Machine Learning Models”  In _Proceedings of the International Conference on Extending Database Technology (EDBT)_ OpenProceedings.org, 2021, pp. 529–534  DOI: 10.5441/002/edbt.2021.63
  * (62) Sebastian Schelter, Tammo Rukat and Felix Bießmann  “Learning to Validate the Predictions of Black Box Classifiers on Unseen Data”  In _Proceedings of the International Conference on Management of Data (SIGMOD)_ ACM, 2020, pp. 1289–1299  DOI: 10.1145/3318464.3380604
  * (63) Sebastian Schelter et al.  “Automating Large-Scale Data Quality Verification”  In _PVLDB_ 11.12, 2018, pp. 1781–1794  DOI: 10.14778/3229863.3229867
  * (64) Sebastian Schelter et al.  “On Challenges in Machine Learning Model Management”  In _IEEE Data Engineering Bulletin_ 41.4, 2018, pp. 5–15  URL: http://sites.computer.org/debull/A18dec/p5.pdf
  * (65) K. P. Sinaga and M.-S. Yang  “Unsupervised k-Means Clustering Algorithm”  In _IEEE access_ 8, 2020, pp. 80716–80727
  * (66) D. J. Slate  “Letter Recognition Dataset” https://archive.ics.uci.edu/ml/datasets/letter+recognition, visited 2022-03-11, 1991
  * (67) C. Song et al.  “Auto-encoder Based Data Clustering”  In _Iberoamerican Congress on Pattern Recognition_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 117–124
  * (68) D. Specht  “A General Regression Neural Network”  In _IEEE Transactions on Neural Networks_ 2, 1991, pp. 568–578  DOI: 10.1109/72.97934
  * (69) Julia Stoyanovich and Bill Howe  “Nutritional Labels for Data and Models”  In _IEEE Data Engineering Bulletin_ 42.3, 2019, pp. 13–23  URL: http://sites.computer.org/debull/A19sept/p13.pdf
  * (70) Jacopo Tagliabue, Ville Tuulos, Ciro Greco and Valay Dave  “DAG Card is the new Model Card”  In _CoRR_ abs/2110.13601, 2021, pp. 1–6  arXiv: https://arxiv.org/abs/2110.13601
  * (71) N. X. Vinh, J. Epps and J. Bailey  “Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance”  In _The Journal of Machine Learning Research_ 11 JMLR. org, 2010, pp. 2837–2854
  * (72) R. Y. Wang and D. M. Strong  “Beyond Accuracy: What Data Quality Means to Data Consumers”  In _J. Manag. Inf. Syst._ 12.4, 1996, pp. 5–33  URL: http://www.jmis-web.org/articles/1002

The Appendix provides some additional plots from the conducted experiments
that were discussed in the report, but moved to the appendix to improve the
readability of the report.

We show in Figure 23, the performance of the classification algorithms when we
decrease the data consistency with $k_{v}=2$. The same for clustering
algorithm is shown in Figure 24. We also included in Figure 25 the plots from
the regression experiments where the uniqueness polluter added duplicates
following a normal distribution.

For better understanding some clustering results, it is beneficial to see the
correlation between the number of clusters identified by the OPTICS and
Autoencoder clustering approaches to their performance. Please note that the
Agglomerative and k-Means / k-Prototypes algorithms are always returning the
expected number of clusters as this is one of their input parameters. The
Gaussian Mixtures algorithm is also coerced to do this; however, it is not
guaranteed to return the correct number of clusters. Therefore, these three
lines commonly overlap and only one of them is visible in the plots. The
number of clusters shown in Figure 26 is averaged over the 5 different runs of
each algorithm on a given dataset, and can therefore also take on floating-
point values.

Finally, as the line plots shown in the clustering result chapter (see Section
6.3) for the Bank dataset are difficult to read because of the shared y-axis
among the different datasets, we decided to also add a focused version of
these plots in Figure 27.

(a) Contraceptive dataset (Scenario 1)

(b) Credit dataset (Scenario 1)

(c) Telco-Churn dataset (Scenario 1)

(d) Contraceptive dataset (Scenario 2)

(e) Credit dataset (Scenario 2)

(f) Telco-Churn dataset (Scenario 2)

(g) Contraceptive dataset (Scenario 3)

(h) Credit dataset (Scenario 3)

(i) Telco-Churn dataset (Scenario 3)

Figure 23: F-1 of the classification algorithms for consistent representation
with $k_{v}=2$.

(a) Houses dataset (Scenario 1)

(b) IMDB dataset (Scenario 1)

(c) Cars dataset (Scenario 1)

(d) Houses dataset (Scenario 2)

(e) IMDB dataset (Scenario 2)

(f) Cars dataset (Scenario 2)

(g) Houses dataset (Scenario 3)

(h) IMDB dataset (Scenario 3)

(i) Cars dataset (Scenario 3)

Figure 24: $R^{2}$ of the regression algorithms for consistent representation
with $k_{v}=2$.

(a) Houses dataset (Scenario 1)

(b) IMDB dataset (Scenario 1)

(c) Cars dataset (Scenario 1)

(d) Houses dataset (Scenario 2)

(e) IMDB dataset (Scenario 2)

(f) Cars dataset (Scenario 2)

(g) Houses dataset (Scenario 3)

(h) IMDB dataset (Scenario 3)

(i) Cars dataset (Scenario 3)

Figure 25: $R^{2}$ of the regression algorithms for uniqueness with duplicate
count sampled by normal distribution.

(a) Letter dataset, expected 26 clusters

(b) Covertype dataset, expected 7 clusters

(c) Bank dataset, expected 6 clusters

(d) Letter dataset, expected 26 clusters

(e) Covertype dataset, expected 7 clusters

(f) Bank dataset, expected 6 clusters

(g) Letter dataset, expected 26 clusters

(h) Covertype dataset, expected 7 clusters

(i) Bank dataset, expected 6 clusters

Figure 26: Average number of clusters identified for completeness, target
class balance, and feature accuracy dimension.

(a) Completeness dimension

(b) Consistent representation dimension

(c) Feature accuracy dimension

(d) Target accuracy dimension

(e) Target class balance dimension

(f) Uniqueness dimension

Figure 27: Average AMI score of the clustering algorithms for the Bank
dataset.