Diane Bouchacourt Centralesupélec

Sebastian Nowozin
email: sebastian.nowozin@microsoft.com

M Pawan

Kumar Centralesupélec

Entropy-based Latent Structured Output Prediction

Recently several generalizations of the popular latent structural SVM framework have been proposed in the literature. Broadly speaking, the generalizations can be divided into two categories: (i) those that predict the output variables while either marginalizing the latent variables or estimating their most likely values; and (ii) those that predict the output variables by minimizing an entropy-based uncertainty measure over the latent space. In order to aid their application in computer vision, we study these generalizations with the aim of identifying their strengths and weaknesses. To this end, we propose a novel prediction criterion that includes as special cases all previous prediction criteria that have been used in the literature. Specifically, our framework's prediction criterion minimizes the Aczél and Daròczy entropy of the output. This in turn allows us to design a learning objective that provides a unified framework (UF) for latent structured prediction. We develop a single optimization algorithm and empirically show that it is as effective as the more complex approaches that have been previously employed for latent structured prediction. Using this algorithm, we provide empirical evidence that lends support to prediction via the minimization of the latent space uncertainty.

Introduction

Structured output prediction methods [START_REF] Bakir | Predicting Structured Data[END_REF][START_REF] Nowozin | Structured learning and prediction in computer vision[END_REF] have gained popularity in computer vision due to their ability to provide an elegant formulation for systems that perform various important visual tasks such as object detection [START_REF] Blaschko | Learning to localize objects with structured output regression[END_REF] or semantic segmentation [START_REF] Kumar | Learning specific-class segmentation from diverse data[END_REF]. In the supervised setting these methods assume that training data is fully labeled. However in many computer vision tasks it can be very expensive, or even impossible, to gather such fully supervised datasets. For example when performing action recognition, we may know that a person is performing an action in the image. However, the exact location of the person may not be known as it is more expensive to obtain bounding box annotations compared to image-level annotations.

In order to learn from weakly supervised datasets (that is, datasets whose samples contain missing information in the annotation), a popular approach is to use the latent structural support vector machine (LSSVM) framework [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF]. The LSSVM framework models the missing information of weakly supervised datasets with latent/hidden variables. Its prediction criterion is the maximization of the joint posterior probability over the output and hidden variables. Its learning objective is an upper bound on a user-specified loss function that provides a measure of the prediction risk. Recently, several generalizations of the LSSVM framework have been proposed. While the generalized frameworks share the common characteristic that their parameters are estimated by minimizing the prediction risk, they differ from each other in the prediction criterion. Specifically, the methods can be separated into two categories. The first category predicts the output while marginalizing over the latent variable or setting it to its most likely value, and the second performs prediction while minimizing the uncertainty over the latent space with the use of an entropy-based uncertainty measure.

In this paper, our goal is to study the LSSVM framework and its generalizations in order to aid their application in computer vision. We propose a natural unified framework that contains all previous loss-based latent structured prediction frameworks as special cases. The UF performs inference of the output variable by minimizing the uncertainty over the hidden variable as measured by the Aczél and Daròczy (AD) entropy. We derive an optimization algorithm based on the concave convex procedure (CCCP) presented in [START_REF] Yuille | The Concave-Convex Procedure (CCCP)[END_REF] for learning the parameters of the UF. This allows us to compare the prediction criterion of all frameworks presented in Section 2 by discounting any variability that may arise due to differences in the optimization algorithm. We tested the UF, LSSVM, and LSSVM's generalizations on the task of multiple gesture recognition from video sequences and action recognition in images. Our experiments convincingly demonstrate that, for large and ambiguous latent spaces, the entropy-based prediction criterion provides more accurate results.

Related Work

Two types of methods have been proposed to perform structured output prediction in the presence of latent variables. With probabilistic methods the parameters are estimated by maximizing the (incomplete) data log-likelihood. One famous example is the Expectation-Maximization (EM) algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF][START_REF] Sundberg | Maximum likelihood theory for incomplete data from an exponential family[END_REF]. EM and its variants [START_REF] Gelman | Bayesian Data Analysis[END_REF][START_REF] Neal | A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF][START_REF] Salojärvi | Expectation maximization algorithms for conditional likelihoods[END_REF] have been widely used to learn the parameters of a model with latent variables.

In this paper, we are primarily interested in the second type of methods where the parameters are learned by minimizing the regularized empirical risk. The risk is measured by a user-specified loss function. The most commonly used example of a loss-based framework is the latent structural support vector machine (LSSVM) [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF]. LSSVM extends structural support vector machines (SSVM) for structured output prediction [START_REF] Taskar | Max-margin Markov networks[END_REF][START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF] to latent variable models. The LSSVM model performs prediction by maximizing the joint posterior probability over the output and hidden variables. The parameters of the model are learned by minimizing an upper bound on the user-defined loss. Due to its simplicity and computational efficiency, the LSSVM formulation has gained popularity among the computer vision community with several applications such as object detection [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Zhu | Latent hierarchical structural learning for object detection[END_REF], image segmentation [START_REF] Kumar | Learning specific-class segmentation from diverse data[END_REF], indoor scene interpretation [START_REF] Wang | Discriminative learning with latent variables for cluttered indoor scene understanding[END_REF] and action classification [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF]. Indeed, its formulation enables LSSVM to be optimized with energy minimization techniques such as graph cuts [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. However, this advantage is not reflected in our experiments as we choose application problems where all output configurations are computable in a computationally feasible manner, in order to remove from our comparison the possible effects of the use of approximation methods.

Recent years have witnessed the development of several generalizations of LSSVM. While all these frameworks estimate the parameters by minimizing an upper bound on the empirical risk, they differ greatly in their prediction criterion and can be divided into two categories. The first category uses marginalization of the latent variables. Schwing et al. [START_REF] Schwing | Efficient structured prediction with latent variables for general graphical models[END_REF] introduce a temperature parameter ǫ and propose a family of models, which we will refer to as the ǫ-framework. The prediction criterion of the ǫframework can range from the maximization over the output and hidden variables (by setting ǫ to the limit value of 0, noted ǫ ց 0, recovering the LSSVM model) to the marginalization over these variables (by setting ǫ = 1). Ping et al. [START_REF] Ping | Marginal structured SVM with hidden variables[END_REF] introduce marginal structured support vector machines (MSSVM). The MSSVM prediction criterion involves marginalizing the latent variables to estimate the probability of output variables. They also describe a more general framework with temperature parameters that includes LSSVM [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF], MSSVM [START_REF] Ping | Marginal structured SVM with hidden variables[END_REF] and the ǫ-framework [START_REF] Schwing | Efficient structured prediction with latent variables for general graphical models[END_REF] as special cases. The second category uses entropy as an uncertainty measure on the value of the hidden variable. Specifically, Miller et al. [START_REF] Miller | Max-margin min-entropy models[END_REF] proposed the max-margin min-entropy (M3E) family of models. M3E models account for uncertainty over the hidden variable by predicting the output with minimal Rényi entropy.

Unlike LSSVM, its generalizations mentioned above have not been widely used by the computer vision community. We believe that the reason for this is three-fold. First, there have been limited experimental results reported in the literature that compare the merits of each of these methods. Second, even in the limited experiments, it is difficult to assess whether the reported improvements of one method over the other are due to a better learning objective or a better optimization algorithm. Third, each method has in the best case a completely different software to the other, and in the worst case no publicly available implementation. This prevents a user, who is primarily interested in exploiting the advances made in machine learning to improve the state of the art in computer vision, to use the more sophisticated learning formulations.

Our goal is to study these generalizations and to define a simple prediction criterion that allows us to construct a Unified Framework (UF) for loss-based latent structured prediction. Our UF recovers all the aforementioned frameworks, that is, LSSVM [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF], MSSVM [START_REF] Ping | Marginal structured SVM with hidden variables[END_REF], the ǫ-framework [START_REF] Schwing | Efficient structured prediction with latent variables for general graphical models[END_REF] and M3E [START_REF] Miller | Max-margin min-entropy models[END_REF] as special cases. Furthermore, it also exposes an extra-degree of freedom that has not yet been explored. We develop an optimization procedure and propose a single simple and efficient algorithm for learning the parameters of the UF. With this setting we are able to compare the prediction criteria of the cited models by discounting the differences that could come from using different optimization algorithms. We built a software implementing the UF and the loss-based models we cited. Our software, as well as all the data required to replicate our experiments, will be made publicly available at the authors homepage.

Our UF generalizes formulations that obtain a point estimate of the model parameters. However a notable framework that is not covered in our generalization is the partially observed Maximum Entropy Discrimination Markov Network (PoMEN) [START_REF] Zhu | Partially observed maximum entropy discrimination Markov networks[END_REF]. The PoMEN model builds on the maximum entropy discrimination Markov Networks (MaxEnDNet) [START_REF] Zhu | Maximum entropy discrimination Markov networks[END_REF], which subsumes SSVM. It combines Bayesian techniques and max-margin learning and its prediction criterion is based on model averaging which results in an advantageous smoothing effect. The conclusions drawn from the current paper lend support to the investigation of entropy-based generalizations of PoMEN.

Preliminaries

In this section we provide notations and definitions used in the rest of the paper. Notations. For simplicity, we assume a discrete setting. We denote the input by x ∈ X , the output by y ∈ Y and the hidden variables by h ∈ H. The value of x is known during both training and testing, the value of y is known only during training and the value of h is unknown during both training and testing. For example when performing multi-class gesture recognition in video sequences, the input x consists of joint coordinates of a person performing a gesture in the sequence. The output y is the gesture class label of the video. In a video sequence, only a small proportion of frames effectively represent the human performing the gesture. It is easy to collect a large number of such video sequences. However it would be time consuming to annotate each frame as containing the gesture or not. Thus we will only consider the label of the gesture performed in a video sequence but not the annotation at the frames level. In other words, we are in the setting of weakly supervised learning. The latent variable h is introduced to take into account this lack of information.

We assume (x, y, h) follows a conditional model:

P (y, h|x; w) ∝ exp 1 ǫ h w T φ(x, y, h) , (1)
where φ : (X , Y, H) → R D refers to the joint feature vector of the input, the output and the hidden variables, and w ∈ R D are the model parameters.

We introduce the temperature parameter ǫ h ∈ [0, 1] in the expression of the joint probability of the output and the hidden variables. The use of ǫ h allows our prediction criterion to range from assigning the latent variable to its most likely value when ǫ h ց 0 to the marginalization over the hidden variables when ǫ h = 1. It follows that

P (y|x; w) ∝ h exp 1 ǫ h w T φ(x, y, h) . (2)
To describe the joint conditional probability distribution of the output and hidden variables (y, h) ∈ Y ×H given an input x ∈ X and model parameters w ∈ R D , P (y, h|x; w), we use the shorthand notation P x . For a fixed output y ∈ Y, P x is a probability distribution of the hidden variable h ∈ H which we denote as Q y x . Note that Q y x is a generalized distribution that need not sum to one. Finally, we denote the conditional probability distribution of the hidden variables given the input, the output and the model parameters, P (h|y, x; w), as P y

x . Aczél and Daròczy entropy. To measure uncertainty we will use the Aczél and Daròczy (AD) entropy (AD) [START_REF] Aczél | Charakterisierung der Entropien positiver Ordnung und der Shannonschen Entropie[END_REF], parametrized by the scalars α and β. Formally, the AD entropy of the generalized distribution is

H α,β (Q y x ; w) = 1 1 -α log h P (y, h|x; w) α+β-1 h P (y, h|x; w) β , ( 3
) with α ≥ 0, α = 1, β ≥ 0, α + β -1 ≥ 0.
The AD entropy has been studied by Aczél and Daròczy [START_REF] Aczél | Charakterisierung der Entropien positiver Ordnung und der Shannonschen Entropie[END_REF] as a natural generalization of the Rényi entropy with an extra scalar parameter β. The AD entropy has since been shown to create a natural family of uncertainty measures, also recovering other existing entropy functions as special cases [START_REF] Esteban | A summary on entropy statistics[END_REF][START_REF] Mathai | Basic Concepts in Information Theory and Statistics: Axiomatic Foundations and Applications[END_REF].

Let us take a closer look at some interesting special cases of the AD entropy. Specifically when β = 1, the AD entropy is equivalent to the Rényi entropy used in the M3E models [START_REF] Miller | Max-margin min-entropy models[END_REF],

H α,1 (Q y x ; w) = 1 1 -α log h P (y, h|x; w) α h P (y, h|x; w) . (4)
When β = 1 and α → ∞, the AD entropy is equivalent to the minimum entropy

H ∞,1 (Q y x ; w) = -log max h P (y, h|x; w). (5)
In other words, the AD entropy for a generalized distribution corresponding to y is obtained by maximizing the joint probability of y and h over the latent variables h. When β = 1 and α → 1, the AD entropy is equivalent to the commonly used Shannon entropy

H 1,1 (Q y x ; w) = -h P (y, h|x; w) log P (y, h|x; w) h P (y, h|x; w) . (6
) When β = 0 and α = 2 , the AD entropy is equivalent to the marginalization over the latent variable:

H 2,0 (Q y x ; w) = -log h P (y, h|x; w) + K, ( 7
)
where K is a constant. In other words, the AD entropy for a generalized distribution corresponding to y is obtained by marginalizing the joint probability of y and h over the latent variables h.

The Unified Framework

In order to facilitate our exploration of the performance of the various generalizations of LSSVM, we would like to obtain a unified criterion for prediction that captures the previously used criteria. In other words, our criterion should include as special cases, (i) the maximization over the output y and the latent variable h; (ii) the maximization over the output y after marginalizing the joint probability over h; and (iii) the maximization over the output y while minimizing the uncertainty over the distribution of h. Furthermore, we would also like to design a learning objective that minimizes an upper bound on the empirical risk based on the prediction criterion, where the risk is measured by a userdefined loss function. We begin by showing that the AD entropy provides a suitable prediction criterion that meets the aforementioned requirements. The identification of the AD entropy as our prediction criterion will allow us to develop a suitable learning objective.

Prediction

We propose to perform prediction for an input x i by minimizing the AD entropy of the generalized distribution over all possible outputs, that is

y i (w) = argmin y H α,β (Q y x i ; w). (8)
Again, let's look at special cases of this prediction procedure. When β = 1, the prediction recovers the prediction task of M3E models [START_REF] Miller | Max-margin min-entropy models[END_REF],

y i (w) = argmin y H α,1 (Q y x i ; w). (9)
Since M3E itself generalizes LSSVM, it follows that our prediction criterion also includes it as a special case. Specifically, β = 1 and α → ∞ , the prediction recovers the prediction task of LSSVM [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF] by performing maximum a posteriori prediction,

y i (w) = argmax y max h log P (y, h|x i ; w). (10)
Similarly when β = 0 and α = 2 , the prediction task is equivalent to the maximization of the marginalized joint probability over the output and hidden variable. This is the prediction setting of MSSVM [START_REF] Ping | Marginal structured SVM with hidden variables[END_REF] and ǫ-framework [START_REF] Schwing | Efficient structured prediction with latent variables for general graphical models[END_REF],

y i (w) = argmax y log h P (y, h|x i ; w). (11)
The following proposition sheds further light on our prediction criterion.

Proposition 1. The AD entropy of the generalized distribution of y can be written as the sum of the negative loglikelihood of y and the AD entropy of the conditional distribution of the hidden variable given the output,

H α,β (Q y x ; w) = -log P (y|x, w) + H α,β (P y x ; w). ( 12
)
Proof. In the supplementary material.

Proposition 1 shows that performing prediction by minimizing the AD entropy is equivalent to predicting the output y which (i) has a high probability, and (ii) minimizes the uncertainty over the hidden variable h. Specifically when β = 0 and α = 2, the term H α,β (P y x ; w) in ( 12) disappears. That means that we do not minimize the uncertainty over the distribution of h and ( 8) and ( 11) are equivalent. This is another way to see how we recover the prediction procedure of the MSSVM and ǫ-framework models.

Learning

Given a training dataset of input-output pairs D = {(x i , y i ), i = 1...N }, we wish to learn the parameters of the model, described by the weight vector w, to be able to predict the output for any input x. We introduce the loss function ∆(y, y i ) with ∆(y, y) = 0 that compares the risk of making the prediction y for the input x i with ground truth output y i .

The parameters of the model are learned by minimizing the following objective function [START_REF] Kumar | Learning specific-class segmentation from diverse data[END_REF].

min w 1 2 ||w|| 2 + C n i ǫ y log y exp 1 ǫ y ∆(y i , y) -ǫ h H α,β (Q y x i ; w) + ǫ h H α,β (Q y i x i ; w) . ( 13
)
We introduce regularization over the parameters of the model w to avoid overfitting the parameters to the training data. Furthermore, we introduce the temperature parameter ǫ y ∈ [0, 1]. When ǫ y ց 0 minimizing objective [START_REF] Kumar | Learning specific-class segmentation from diverse data[END_REF] results in maximizing the margin between the AD entropy of the ground truth value of the output and all other values of the output. For other values of ǫ y , the objective function replaces the maximization by a soft max (log-sum-exp) function.

Proposition 2 shows that the optimization procedure of ( 13) minimizes an upper bound on the user-defined loss.

Proposition 2. Objective (13) minimizes an upper bound on the loss ∆(y i , y i (w)) where y i is the ground truth output of training example i and y i (w) is the predicted output. This upper-bound is tightest when ǫ y ց 0.

Proof. In the supplementary material.

Our objective function [START_REF] Kumar | Learning specific-class segmentation from diverse data[END_REF] naturally derives from our prediction procedure and allow us to upper bound the userdefined loss. Furthermore we show by looking at special cases that it recovers the objective functions of the models we want to unify. Specifically when β = 1, ǫ y ց 0, ǫ h = 1 we retrieve the objective function used in training of the M3E models [START_REF] Miller | Max-margin min-entropy models[END_REF], which maximizes the margin between the entropy of the ground truth output value and all other outputs:

min w 1 2 ||w|| 2 + C n i max y ∆(y i , y) -H α,1 (Q y x i ; w) + H α,1 (Q y i x i ; w) . (14)
From the M3E models, taking α → ∞ recovers LSSVM [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF]. Thus when β = 1, ǫ y , ց 0, ǫ h = 1, α → ∞ the learning objective is equivalent to the learning problem of the LSSVM:

min w 1 2 ||w|| 2 + C n i max y×h ∆(y i , y) + w T φ(x i , y, h) - C n i max h w T φ(x i , y i , h). (15)
When β = 0, α = 2, ǫ y , ց 0, ǫ h = 1, the log-sum-exp function over y approximates the max function and we end up maximizing the output y while marginalizing the hidden variable h. Thus (13) becomes equivalent to the optimization problem of the MSSVM [START_REF] Ping | Marginal structured SVM with hidden variables[END_REF]:

min w 1 2 ||w|| 2 + C n i max y ∆(y i , y) + log h exp(w T φ(x i , y, h)) - C n i log h exp w T φ(x i , y i , h) . (16)
Similarly when β = 0, α = 2, ǫ y = ǫ h we recover the same objective to minimize as in the ǫ-framework [START_REF] Schwing | Efficient structured prediction with latent variables for general graphical models[END_REF], that is,

min w 1 2 ||w|| 2 + C n i ǫ log y exp ∆(y i , y) + w T φ(x i , y, h) ǫ - C n i ǫ log h exp w T φ(x i , y i , h) ǫ . (17)
Figure 1 shows that our framework gathers all models presented in Section 2 with specific parameters values. We refer the reader to the supplementary material for more details.

Optimization method

We propose to use a common algorithm for all methods covered by the UF, which is computationally efficient. This allows us to compare the prediction criterion of all these models independently of their specific methods for solving their optimization problem. We derive an optimization procedure for learning the parameters of the UF. This procedure works for every setting of parameters of the UF. In other words it works for every model presented in Section 2. The optimization function of problem ( 13) is not convex. In order to obtain an approximate solution, we write the objective function of (13) as a difference of convex (DC) functions [START_REF] Yuille | The Concave-Convex Procedure (CCCP)[END_REF]. To this end, it would be helpful to introduce the following shorthand notations in the case α > 1:

UF α, β, ǫ y , ǫ h M3E [17] α ≥ 0, β = 1, ǫ y ց 0, ǫ h = 1 LSSVM [10, 28] α → ∞, β = 1, ǫ y ց 0, ǫ h = 1 or α = 2, β = 0, ǫ y = ǫ h ց 0 MSSVM [21] α = 2, β = 0, ǫ y ց 0, ǫ h = 1 ǫ-framework [23] α = 2, β = 0, ǫ y = ǫ h ∈ (0, 1) α → ∞ ǫ y = ǫ h ց 0
• F + α,β (y, w) = -ǫ h 1 1 -α log h P (y, h|x i ; w) α+β-1 , • F - α,β (y, w) = -ǫ h 1 1 -α log h P (y, h|x i ; w) β , • G + α,β (y i , w) = -ǫ h 1 1 -α log h P (y i , h|x i , w) β , • G - α,β (y i , w) = -ǫ h 1 1 -α log h P (y i , h|x i , w) α+β-1 .
The functions F + α,β (y, w), F - α,β (y, w), G + α,β (y i , w), G - α,β (y i , w) are convex with respect to w. Their definitions are trivially inferred in the case α < 1: Proposition 3. The optimization problem (13) can be equivalently written as a difference of convex (DC) functions for any values of α ≥ 0, β ≥ 0 using the following formulation:

min w 1 2 ||w|| 2 + C n ǫ y i log y exp 1 ǫ y ∆(y i , y) + F + α,β (y, w) -F - α,β (y, w) + G + α,β (y i , w) -G - α,β (y i , w) , (18)
where F + α,β (y, w), F - α,β (y, w), G + α,β (y i , w), and G - α,β (y i , w) are convex. Proof. In the supplementary material. This results in Algorithm 1 for training the UF. Algorithm 1 is similar to standard concave convex procedure (CCCP) [START_REF] Yuille | The Concave-Convex Procedure (CCCP)[END_REF]. During step 1 of Algorithm 1, we solve the convex optimization problem [START_REF] Nowozin | Structured learning and prediction in computer vision[END_REF]:

w t+1 = argmin w 1 2 ||w|| 2 + C n ǫ y i log y exp 1 ǫ y ∆(y i , y) + F + α,β (y, w) -T F - α,β y,w t (w) + G + α,β (y i , w) -T G - α,β y i ,w t (w) . ( 19
)
During step 1, F - α,β (y, w) and G - α,β (y i , w) are replaced by their first order Taylor expansion:

T F - α,β y,w t (w) = F α,β (y, w t ) -+ (w -w t ) T ∇ w F - α,β (y, w)| w t , T G - α,β y i ,w t (w) = G α,β (y i , w t ) -+ (w -w t ) T ∇ w G - α,β (y i , w)| w t . ( 20
)
We denote by ∇ w F - α,β (y, w)| w t the gradient of F - α,β (y, w) with respect to w estimated at w t and similarly ∇ w G - α,β (y i , w)| w t .

Algorithm 1: Algorithm for trainin UF We solve the optimization problem (19) of step 1 in Algorithm 1 by performing gradient descent with a step size found by line search. We refer the reader to the supplementary material for details on our gradient descent procedure.

Data: D = {(x i , y i ), i = 1...N } Result: Model parameter w initialize w = w 0 , t = 0; obj(w, w t ) = 1 2 ||w|| 2 + C n ǫ y i log y exp 1 ǫ y ∆(y i , y) + F + α,β (y, w) -T F - α,β y,w t (w) + G + α,β (y i , w) -T G - α,β y i ,w t (w) (21

Experiments

We performed experiments to compare the UF, LSSVM [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF], MSSVM [START_REF] Ping | Marginal structured SVM with hidden variables[END_REF], the ǫ-framework [START_REF] Schwing | Efficient structured prediction with latent variables for general graphical models[END_REF], M3E models [START_REF] Miller | Max-margin min-entropy models[END_REF] and replications of these models by the UF. Our goal with these experiments is to assess which is the most accurate of prediction criteria between the two types of models generalizing LSSVM (described in Section 2), regardless of their specific optimization algorithm. To this end, we compare them and their replications using the UF on two different tasks. In all figures the sign ∼ means that the UF's parameters were set to replicate an existing model.

Binary action classification

We start our empirical comparison on an example where the latent space size is small and the uncertainty over the hidden variable is low. Specifically, we perform the following experiment of binary action classification over the 10 classes of the PASCAL VOC 2011 dataset.

Pascal VOC dataset. We use the "trainval" dataset of the PASCAL VOC 2011 [START_REF] Everingham | The pascal visual object classes (VOC) challenge[END_REF] action classification dataset, consisting of 2424 images depicting 10 action classes. We used the 10 classes of the dataset. For each image we are provided the bounding boxes of the persons in the image and its action class. However, in our experiments, we discard the bounding box information and instead model it using a latent variable.

Modelling and features. The score of a bounding box in the image x is w T φ(x, y, h) = w T y φ(x, h) where w y are the parameters that correspond to the label y and φ(x, h) is the feature vector extracted from the bounding box h. Similar to [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF], we consider the bounding boxes of the image with the top 20 scores found by a standard person detector [START_REF] Felzenszwalb | Discriminatively trained deformable part models[END_REF]. Thus we reduce the uncertainty on the latent space since we take only the top scoring bounding boxes and we work with a small latent space size. The feature vector φ(x, h) consists of the standard poselet-based feature vector [START_REF] Maji | Action recognition from a distributed representation of pose and appearance[END_REF], that is a 2404 dimensional vector consisting of 2400 activation scores of action specific poselets and 4 object activation scores. We added the score given by the person detector [START_REF] Felzenszwalb | Discriminatively trained deformable part models[END_REF] making φ(x, h) a 2405 dimensional feature vector. The loss ∆ is the standard 0-1 loss.

Experimental setting. We split the dataset into 1940 training images and 484 validation images. Hyper parameters are chosen via 5 fold cross-validation. We use four random seed values in order to mitigate possible effects of the initialization; this is to ensure that the nonconvexity of the optimization objective does not lead to poor results by local minima. For each fold, we report the test error corresponding to the seed with the lowest training objective value. All models are initialized with LSSVM [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF] except for M3E with α → ∞ that includes random initialization of the hidden variable value. The convergence tolerance is set to λ = 0.01. For each model, we tested the following range of parameters: C = [0.1, 1, 10, 100, 1000], ǫ = [0.001, 0.01, 0.1, 1] (referring to the parameter of the ǫ-framework), ǫ h = [0.001, 0.01, 0.1, 1.0], α = [0.01, 0.1, 2, 100, 1000, 10000] and β = [0.0, 0.5, 1.0]. In terms of computing CPU times, all models require comparable times. We refer the reader to the supplementary material for detailed timing.

Results. Figure 2 shows the mean loss on the test set over the 10 classes of each model with best cross-validated parameters (averaged over the 5 folds). We refer the reader to the supplementary material for additional details regarding the experimental setup and the results. From figure 2, we see that the performances of UF as a replication and the corresponding existing model are similar. We see that predicting the output by marginalizing the output and hidden variables as done by MSSVM is the less accurate criterion. Our UF and M3E models provide slightly better performances than LSSVM, MSSVM and the ǫ-framework.

LS SV M M 3E , α → ∞ M 3E M SS V M ǫ-fr am ew or k U F U F ∼ LS SV M U F ∼ M 3E U F ∼ M SS V M
For clarity purposes we do not report the best parameters chosen by cross-validation but they are available in the supplementary material. In most cases the set of UF parameters chosen by cross-validation boils down to a prediction criterion that maximizes over the output and hidden variables. Similarly, the best α chosen for the M3E models is of high value. In other words, M3E recovers LSSVM. The ǫframework chooses a small value of ǫ, which also approximates LSSVM. Thus for this specific task there is a small gain to be made from taking into account the uncertainty over the hidden variable. This comes at the cost of using a more complicated model with more parameters to crossvalidate. This result is aligned with the fact that the size of the latent space is small (we use 20 bounding boxes) and that uncertainty over the hidden variable is reduced since we consider top scoring bounding boxes.

Multi-class gesture recognition

We now explore an experiment where the uncertainty over the value of the hidden variable is high and the latent space is large. To do so, we tested the UF and the loss-based models presented in Section 2 on the task of gesture recognition in video sequences. Given a set of video sequences, our goal is to learn to classify, among c possible classes of gestures, the gesture performed in a video sequence.

MSRC-12.

The MSRC-12 data set [START_REF] Fothergill | Instructing people for training gestural interactive systems[END_REF] contains 594 sequences of motion capture data, recording the 3D world position of 20 joints in the human body using a Kinect sensor from a population of 30 individuals. In each sequence the actor performs one type of gesture repeatedly, typically 10 times, and each instance of the gesture is marked at a typical frame. The original purpose of the data set was to enable research into low latency gesture detection [START_REF] Nowozin | Action points: A representation for low-latency online human action recognition[END_REF]. However, it has since been used to classify the sequence as a whole [START_REF] Fothergill | Instructing people for training gestural interactive systems[END_REF][START_REF] Lehrmann | Efficient nonlinear Markov models for human motion[END_REF]. We also perform sequence classification but do not use the individual frame-level annotations. Instead, as training data we use only the sequence class label. This is a realistic assumption for example in an interactive setting when the user is instructed by a system to perform a gesture for an initial training phase. In this case we only know that a gesture of a given class will be performed but do not know when the user will perform it.

Noisy MSRC-12 dataset. In order to evaluate the behavior of the different models in presence of noisy data, we corrupt the MSRC-12 dataset by adding random Gaussian noise with zero mean and various standard deviations. In particular we add noise to each elements of all frames' feature vectors. We use three values of standard deviations: σ = [1cm, 5cm, 8cm].

Modelling and features. The input data x consists of 3D world position of a person performing a gesture. The output y is the class of the gesture performed in the video sequence. In a video sequence only a few percent of the video frames effectively contain the person performing the gesture. We consider the training data as weakly labeled, i.e. the video sequences are only labeled at the sequence level and each frame is not individually annotated as containing the gesture or not. We use the latent variable h to model this lack of information. The size of the latent space is the number of frames per video sequence, that is on average 1200 frames per sequence. The score of a specific frame in a video sequence x is w T φ(x, y, h) = w T y φ(x, h) where w y are the parameters that correspond to the label y and φ(x, h) is the feature vector extracted from the video sequence frame h. We take the same features derived from 3D joint locations as in [START_REF] Fothergill | Instructing people for training gestural interactive systems[END_REF][START_REF] Lehrmann | Efficient nonlinear Markov models for human motion[END_REF][START_REF] Nowozin | Action points: A representation for low-latency online human action recognition[END_REF], obtaining a feature vector φ(x, h) of dimension 130. The loss ∆ is the standard 0-1 loss.

Experimental setting. We use the 594 sequences from the MSRC-12 dataset. We divide this dataset into five folds, each fold containing 20% of the trainval data set for testing and 80% for training, using stratified sampling over class labels in order to ensure a uniform distribution over classes. As in the action classification experiment of Section 6.1, hyper parameters are cross-validated over 5 folds and we use 4 random seeds for initialization and for each fold, we report the test error corresponding to the seed with the lowest training objective value. All models are initialized with LSSVM [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF] except for M3E with α → ∞. The convergence tolerance is set to λ = 0.01. We tested the same range of parameters as in the binary action classification experiment except for the parameter C we used the values [1, 10, 100, 1000, 10000]. When looking at CPU times, all models require comparable times. We refer the reader to the supplementary material for detailed timing.

Results. Table 1 reports the best parameters chosen by cross-validation for the UF. Table 1 shows that the best parameters combination (ǫ h , α, β) always take in account the AD entropy of the hidden variable and the term H α,β (P y x ; w) in ( 12) is never set to 0. This would be the case if we had (α = 2, β = 0) or (α → ∞, β = 1). Thus the UF is never boiling down to either LSSVM, MSSVM or the ǫ-framework. Recall that UF recovers all models with the use of the same algorithm. This means that regardless of the algorithm used to solve the minimization problem during learning, predicting the output variables by minimizing the uncertainty over the latent space is a more relevant method than marginalizing the latent variables or estimating their most likely values. Figure 3b shows the average loss on the test set for LSSVM, M3E and MSSVM, and their replication with the UF. This figure shows two things. First, by looking at the performances of their replication by the UF, we can compare LSSVM, MSSVM and M3E models without taking into account their specific training algorithm. Second, this figure also shows how the UF replicates existing models. In the cases when the UF replicates LSSVM and MSSVM results are similar, this was expected since the algorithm we derived for training the UF is similar to the specific algorithm of these models. When the UF replicates M3E, results are also similar even if the optimization procedures are different (the M3E models use a trust-region based algorithm to solve the optimization problem). From these two figures 3a and 3b we conclude that entropy-based models (either M3E or the UF) give significantly better performances at all noise levels. We refer the reader to the supplementary material for p-values and comparison at statistical significance level of 0.05.

σ = 0cm σ = 1cm σ = 5cm σ = 8cm ǫ h = 1, α = 0.01, β = 1 ǫ h = 1, α = 2, β = 0.5 ǫ h = 1, α = 0.1, β = 1 ǫ h = 1, α = 0.1, β = 1
Figure 4 shows the scoring of the UF on an example "bowing" gesture of the non-noisy MSRC-12 dataset. A 3D representation of the frame feature vector is added in the upper part of the plot. For the ground-truth label, the UF gives high score at typical frames of the video sequence when the person is effectively bowing, and a low score in between. The scores of all others labels (shown in grey) are smaller than the smallest score of the ground-truth label frames.

Discussion

We developed a Unified Framework (UF) by defining a simple prediction criterion for generalizations of LSSVM. By developing an optimization algorithm for learning the parameters of the UF, we evaluate each prediction criterion without taking into account the differences in performances that could arise from using their specific optimization algorithm. Our experimental results show that the use of the minimization of the latent space uncertainty is an accurate prediction criterion when the size of the latent space is large and when there is uncertainty on the hidden variable. The UF also offers an additional advantage, namely, the use of the extra parameter β. This has yet to be explored thoroughly, and could lead to improved performance. As a direction for future work, we suggest to use a fully Bayesian setting with prior distributions over the UF parameters. We also propose to incorporate the UF in the framework of deep learning to further improve the performance of this popular framework.

Acknowlegements

This work is co-funded by the Microsoft Research PhD Scholarship Programme in EMEA (Europe, Middle East, Africa) and Ecole Centrale Paris.

Figure 1 :

 1 Figure 1: Equivalence of UF with existing models.

Figure 2 :

 2 Figure 2: Test loss mean on the 10 classes (in %) ± standard error of the mean (in %) with crossvalidated parameters on the PAS-CAL VOC 11 dataset, after averaging on the 5 folds.

Figure

  Figure3ashows the average loss on the test set for each model with respect to the noise level corrupting the dataset.

  Existing models (line curves) and their replication by the UF (dashed curves).

Figure 3 :

 3 Figure 3: Test loss (%) on the MSRC-12 dataset averaged on 5 folds, per noise level. Each model is shown with best cross-validated parameters.

Figure 4 :

 4 Figure 4: Scoring of the UF on an example "bowing" gesture of the non noisy MSRC-12 dataset. Upper part of the plot shows the scoring for the ground truth label (in red), and all other labels in grey. Lower part of the plot shows the location of the action frames as per MSRC-12 ground truth (we do not use this frame-level annotation).

Table 1 :

 1 Cross-validated parameters for the UF.


domain: spi.auto info math

text:
Puneet K Dokania Centralesupélec

M Pawan Kumar
email: pawan.kumar@ecp.fr

Parsimonious Labeling

We propose a new family of discrete energy minimization problems, which we call parsimonious labeling. Our energy function consists of unary potentials and high-order clique potentials. While the unary potentials are arbitrary, the clique potentials are proportional to the diversity of the set of unique labels assigned to the clique. Intuitively, our energy function encourages the labeling to be parsimonious, that is, use as few labels as possible. This in turn allows us to capture useful cues for important computer vision applications such as stereo correspondence and image denoising. Furthermore, we propose an efficient graph-cuts based algorithm for the parsimonious labeling problem that provides strong theoretical guarantees on the quality of the solution. Our algorithm consists of three steps. First, we approximate a given diversity using a mixture of a novel hierarchical P n Potts model. Second, we use a divide-andconquer approach for each mixture component, where each subproblem is solved using an efficient α-expansion algorithm. This provides us with a small number of putative labelings, one for each mixture component. Third, we choose the best putative labeling in terms of the energy value. Using both synthetic and standard real datasets, we show that our algorithm significantly outperforms other graph-cuts based approaches.

Introduction

The labeling problem provides an intuitive formulation for several tasks in computer vision and related areas. Briefly, the labeling problem is defined using a set of random variables, each of which can take a value from a finite and discrete label set. The assignment of values to all the variables is referred to as a labeling. In order to quantitatively distinguish between the large number of putative labelings, we are provided with an energy function that maps a labeling to a real number. The energy function consists of two types of terms: (i) the unary potential, which depends on the label assigned to one random variable; and (ii) the clique potential, which depends on the labels assigned to a subset of random variables. The goal of the labeling problem is to obtain the labeling that minimizes the energy.

A well-studied special case of the labeling problem is metric labeling [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF][START_REF] Kleinberg | Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields[END_REF]. Here, the unary potentials are arbitrary. However, the clique potentials are specified by a user-defined metric distance function of the label space. Specifically, the clique potentials satisfy the following two properties: (i) each clique potential depends on two random variables; and (ii) the value of the clique potential (also referred to as the pairwise potential) is proportional to the metric distance between the labels assigned to the two random variables. Metric labeling has been used to formulate several problems in low-level computer vision, where the random variables correspond to image pixels. In such scenarios, it is natural to encourage two random variables that correspond to two nearby pixels in the image to take similar labels. However, by restricting the size of the cliques to two, metric labeling fails to capture more informative highorder cues. For example, it cannot encourage an arbitrary sized set of similar pixels (such as pixels that define a homogeneous superpixel) to take similar labels.

We propose a natural generalization of the metric labeling problem for high-order potentials, which we call parsimonious labeling. Similar to metric labeling, our energy function consists of arbitrary unary potentials. However, the clique potentials can be defined on any subset of random variables, and their value depends on the set of unique labels assigned to the random variables in the clique. In more detail, the clique potential is defined using the recently proposed notion of a diversity [START_REF] Bryant | Hyperconvexity and tight-span theory for diversities[END_REF][START_REF] Bryant | Diversities and the geometry of hypergraphs[END_REF], which generalizes metric distance functions to all subsets of the label set. By minimizing the diversity, our energy function encourages the labeling to be parsimonious, that is, use as few labels as possible. This in turn allows us to capture useful cues for important low-level computer vision applications.

In order to be practically useful, we require a computationally feasible solution for parsimonious labeling. To this end, we design a novel three step algorithm that uses an efficient graph cuts based method as its key ingredient. The first step of our algorithm approximates a given diversity as a mixture of a novel hierarchical P n Potts model (a generalization of the P n Potts model [START_REF] Kohli | P3 & beyond: Solving energies with higher order cliques[END_REF]). The second step of our algorithm solves the labeling problem correspond-ing to each component of the mixture via a divide-andconquer approach, where each subproblem is solved using α-expansion [START_REF] Veksler | Efficient graph-based energy minimization methods in computer vision[END_REF]. This provides us with a small set of putative labelings, each corresponding to a mixture component. The third step of our algorithm chooses the putative labeling with the minimum energy. Using both synthetic and real datasets, we show that our overall approach provides accurate results for various computer vision applications.

Related Work

In last few years the research community has witnessed many successful applications of high-order random fields to solve low level vision related problems such as object segmentation [START_REF] Delong | Fast approximate energy minimization with label costs[END_REF][START_REF] El-Zehiry | Fast global optimization of curvature[END_REF][START_REF] Kohli | Robust higher order potentials for enforcing label consistency[END_REF][START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF][START_REF] Tarlow | Hop-map: Efficient message passing with high order potentials[END_REF][START_REF] Vicente | Joint optimization of segmentation and appearance models[END_REF], disparity estimation [START_REF] Jung | Stereo reconstruction using high order likelihood[END_REF][START_REF] Woodford | Global stereo reconstruction under second order smoothness priors[END_REF], and image restoration [START_REF] Lan | Efficient belief propagation with learned higher-order markov random fields[END_REF]. In this work, our focus is on methods that (i) rely on efficient move-making algorithms based on graph cuts; (ii) provide a theoretical guarantee on the quality of the solution. Below, we discuss the work most closely related to ours in more detail.

Kohli et al. [START_REF] Kohli | P3 & beyond: Solving energies with higher order cliques[END_REF] proposed the P n Potts model, which enforces label consistency over a set of random variables. In [START_REF] Kohli | Robust higher order potentials for enforcing label consistency[END_REF], they presented a robust version of the P n Potts model that takes into account the number of random variables that have been assigned an inconsistent label. Both the P n Potts model and its robust version lend themselves to the efficient α-expansion algorithm [START_REF] Kohli | P3 & beyond: Solving energies with higher order cliques[END_REF][START_REF] Kohli | Robust higher order potentials for enforcing label consistency[END_REF]. Furthermore, the α-expansion algorithm also provides a multiplicative bound on the energy of the estimated labeling with respect to the optimal labeling. While the robust P n Potts model has been shown to be very useful for semantic segmentation, our generalization of the P n Potts model offers a natural extension of the metric labeling problem and is therefore more widely applicable to several low-level vision tasks.

Delong et al. [START_REF] Delong | Fast approximate energy minimization with label costs[END_REF] proposed a global clique potential (label cost) that is based on the cost of using a label or a subset of labels in the labeling of the random variables. Similar to the P n Potts model, the label cost based potential can also be minimized using α-expansion. However, the theoretical guarantee provided by α-expansion is an additive bound, which is not invariant to reparameterization of the energy function. Delong et al. [START_REF] Delong | Minimizing energies with hierarchical costs[END_REF] also proposed an extension of their work to hierarchical costs. However, the assumption of a given hierarchy over the label set limits its applications.

Ladicky et al. [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] proposed a global co-occurrence cost based high order model for a much wider class of energies that encourage the use of a small set of labels in the estimated labeling. Theoretically, the only constraint that [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] enforces in high order clique potential is that it should be monotonic in the label set. In other words, [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] can be regarded as a generalization of parsimonious labeling. However, they approximately optimize an upperbound on the actual energy function, which does not provide any optimality guarantees. In our experiments, we demonstrate that our move-making algorithm significantly outperforms their ap-proach for the special case of parsimonious labeling.

Fix et al. [START_REF] Fix | A primal-dual algorithm for higher-order multilabel markov random fields[END_REF] proposed an algorithm (SoSPD) for highorder random fields with arbitrary clique potentials. Each move of this algorithm requires us to approximately upperbound the clique potential into a submodular function and then optimize it using the submodular max-flow algorithm [START_REF] Kolmogorov | Minimizing a sum of submodular functions[END_REF]. We show that our move making algorithm for parsimonious labeling has a much stronger multiplicative bound and better time complexity compared to [START_REF] Fix | A primal-dual algorithm for higher-order multilabel markov random fields[END_REF].

Preliminaries

The labeling problem. Consider a random field defined over a set of random variables

x = {x 1 , • • • , x N } ar- ranged in a predefined lattice V = {1, • • • , N }. Each random variable can take a value from a discrete label set L = {l 1 , • • • , l H }.
Furthermore, let C denote the set of maximal cliques. Each maximal clique consists of a set of random variables that are all connected to each other in the lattice. A labeling is defined as the assignment or mapping of random variables to the labels. To assess the quality of each labeling x we define an energy function as:

E(x) = i∈V θ i (x i ) + c∈C θ c (x c ). (1)
where θ i (x i ) is the unary potential of assigning a label x i to the variable i, and θ c (x c ) is the clique potential for assigning the labels x c to the variables in the clique c. Clique potentials are assumed to be non-negative. As will be seen shortly, this assumption is satisfied by the new family of energy functions proposed in our paper. The total number of putative labelings is H N , each of which can be assessed using its corresponding energy value. Within this setting, the labeling problem is to find the labeling corresponding to the minimum energy according to the function [START_REF] Pawan Kumar | On approximating arbitrary metrics by tree metrics[END_REF]. Formally, the labeling problem is: x * = argmin x E(x).

P n Potts model. An important special case of the labeling problem, which will be used throughout this paper, is defined by the P n Potts model [START_REF] Kohli | P3 & beyond: Solving energies with higher order cliques[END_REF]. The P n Potts model is a generalization of of the well known Potts model [START_REF] Potts | Some generalized order-disorder transformations[END_REF] for high-order energy functions (cliques can be of arbitrary sizes). For a given clique, the P n Potts model is defined as:

θ c (x c ) ∝ γ k , if x i = l k , ∀i ∈ c, γ max , otherwise, (2)
where γ k is the cost of assigning all the nodes to the label l k ∈ L, and γ max > γ k , ∀l k ∈ L. Intuitively, the P n Potts model enforces label consistency by assigning the cost of γ max if there are more than one label in the given clique.

α-expansion for P n Potts model. In order to solve the labeling problem corresponding to the P n Potts model, Kohli et al. [START_REF] Kohli | P3 & beyond: Solving energies with higher order cliques[END_REF] proposed to use the α-expansion algorithm [START_REF] Veksler | Efficient graph-based energy minimization methods in computer vision[END_REF]. The α-expansion algorithm starts with an initial labeling, for example, by assigning each random variable to the label l 1 . At each iteration, the algorithm moves to a new labeling by searching over a large move space. Here, the move space is defined as the set of labelings where each random variable is either assigned its current label or the label α. The key result that makes α-expansion a computationally feasible algorithm for the P n Potts model is that the minimum energy labeling within a move-space can be obtained using a single minimum st-cut operation on a graph that consists of a small number (linear in the size of the variables and the cliques) of vertices and arcs. The algorithm terminates when the energy cannot be reduced further for any choice of the label α. We refer the reader to [START_REF] Kohli | P3 & beyond: Solving energies with higher order cliques[END_REF] for further details.

Multiplicative Bound. An intuitive and commonly used measure of the accuracy of an approximation algorithm is the multiplicative bound. Formally, the multiplicative bound of a given algorithm is said to be B if the following condition is satisfied for all possible values of unary potential θ i (.), and clique potentials θ c (x c ):

i∈V θ i (x i ) + c∈C θ c (x c ) ≤ i∈V θ i (x * i ) + B c∈C θ c (x * c ). (3)
Here, x is the labeling estimated by the algorithm and x * is a globally optimal labeling. By definition of an optimal labeling (one that has the minimum energy), the multiplicative bound will always be greater than or equal to one [START_REF] Kumar | Rounding-based moves for metric labeling[END_REF]. The α-expansion algorithm for the P n Potts model has the multiplicative bound of λ min(M, |L|), where, M is the size of the largest clique, |L| is the number of labels, and λ = γ max γ min , where γ min = min xc,θc(xc) =0 θ c (x c ) and γ max = max xc θ c (x c ) [START_REF] Gould | Alphabet soup: A framework for approximate energy minimization[END_REF].

Parsimonious Labeling

The parsimonious labeling problem is defined using an energy function that consists of unary potentials and clique potentials defined over cliques of arbitrary sizes. While the parsimonious labeling problem places no restrictions on the unary potentials, the clique potentials are specified using a diversity function [START_REF] Bryant | Hyperconvexity and tight-span theory for diversities[END_REF]. Before describing the parsimonious labeling problem in detail, we briefly define the diversity function for the sake of completion. Definition 1. A diversity is a pair (L, δ), where L is the label set and δ is a non-negative function defined on subsets of L, δ : Γ → R, ∀Γ ⊆ L, satisfying :

• Non Negativity: δ(Γ) ≥ 0, and δ(Γ) = 0, if and only if, |Γ| ≤ 1.

• Triangular Inequality: if Γ 2 = ∅, δ(Γ 1 ∪ Γ 2 ) + δ(Γ 2 ∪ Γ 3 ) ≥ δ(Γ 1 ∪ Γ 3 ), ∀Γ 1 , Γ 2 , Γ 3 ⊆ L. • Monotonicity: Γ 1 ⊆ Γ 2 implies δ(Γ 1 ) ≤ δ(Γ 2 ).
Using a diversity function, we can define a clique potential as follows. We denote by Γ(x c ) the set of unique labels in the labeling of the clique c. Then, θ c (x c ) = w c δ(Γ(x c )), where δ is a diversity function and w c is the non-negative weight corresponding to the clique c. Formally, the parsimonious labeling problem amounts to minimizing the following energy function:

E(x) = i∈V θ i (x i ) + c∈C w c δ(Γ(x c )). (4)
Therefore, given a clique x c and the set of unique labels Γ(x c ) assigned to the random variables in the clique, the clique potential function for the parsimonious labeling problem is defined using δ(Γ(x c )), where δ : Γ(x c ) → R is a diversity function.

Intuitively, diversities enforces parsimony by choosing a solution with fewer unique labels from a set of equally likely solutions. This is an essential property in many vision problems, for example, in the case of image segmentation, we would like to see label consistency within superpixels in order to preserve discontinuity. Unlike the P n Potts model the diversity does not enforce the label consistency very rigidly. It gives monotonic rise to the cost based on the number of labels assigned to the given clique.

An important special case of the parsimonious labeling problem is the metric labeling problem, which has been extensively studied in computer vision [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF][START_REF] Kumar | MAP estimation of semi-metric MRFs via hierarchical graph cuts[END_REF] and theoretical computer science [START_REF] Chekuri | Approximation algorithms for the metric labeling problem via a new linear programming formulation[END_REF][START_REF] Kleinberg | Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields[END_REF]. In metric labeling, the maximal cliques are of size two (pairwise) and the clique potential function is a metric distance function defined over the labels. Recall that a distance function d : L × L → R is a metric if and only if: (i) d(., .) ≥ 0; (ii) d(i, j) + d(j, k) ≥ d(i, k), ∀i, j, k; and (iii) d(i, j) = 0 if and only if i = j. Notice that there is a direct link between the metric distance function and the diversities. Specifically, metric distance functions are diversities defined on subsets of size 2. In other words, diversities are the generalization of the metric distance function and boil down to a metric distance function if the input set is restricted to the subsets with cardinality of at most two. Another way of understanding the connection between metrics and diversities is that every diversity induces a metric. In other words, consider d(l i , l i ) = δ(l i ) = 0 and d(l i , l j ) = δ({l i , l j }). Using the properties of diversities, it can be shown that d(•, •) is a metric distance function. Hence, in case of energy function defined over pairwise cliques, the parsimonious labeling problem reduces to the metric labeling problem.

In the remaining part of this section we talk about a specific type of diversity called the diameter diversity. We show its relation with the well known P n Potts model. Furthermore, we propose a hierarchical P n Potts model based on the diameter diversity defined over a hierarchical clustering (defined shortly). However, note that our approach is applicable to any general parsimonious labeling problem. Figure 1: An example of r-HST for r = 2. The cluster associated with root p contains all the labels. As we go down, the cluster splits into subclusters and finally we get the singletons, the leaf nodes (labels). The root is at depth of 1 (τ = 1) and leaf nodes at τ = 3. The metric defined over the r-HST is denoted as d t (., .), the shortest path between the inputs. For example, d t (l 1 , l 3 ) = 18 and d t (l 1 , l 2 ) = 6. The diameter diversity for the subset of labels at cluster p is max {li,lj }∈{l1,l2,l3,l4} d t (l i , l j ) = 18.

Diameter Diversity. In this work, we are primarily interested in the diameter diversity [START_REF] Bryant | Hyperconvexity and tight-span theory for diversities[END_REF]. Let (L, δ) be a diversity and (L, d) be the induced metric of (L, δ), where d : L × L → R and d(l i , l j ) = δ({l i , l j }), ∀l i , l j ∈ L, then for all Γ ⊆ L, the diameter diversity is defined as:

δ dia (Γ) = max li,lj ∈Γ d(l i , l j ). (5)
Clearly, given the induced metric function defined over a set of labels, diameter diversity over any subset of labels gives the measure of the dissimilarity (or diversity) of the labels. More the dissimilarity, based on the induced metric function, higher is the diameter diversity. Therefore, using diameter diversity as clique potentials enforces the similar labels to be together. Thus, a special case of parsimonious labeling in which the clique potentials are of the form of diameter diversity can be defined as below:

E(x) = i∈V θ i (x i ) + c∈C w c δ dia (Γ(x c )). (6)
Notice that the diameter diversity defined over uniform metric is nothing but the P n Potts model where γ i = 0. In what follows we define a generalization of the P n Potts model, the hierarchical P n Potts model, which will play a key role in the rest of the paper.

The Hierarchical P n Potts Model. The hierarchical P n Potts model is a diameter diversity defined over a special type of metric known as the r-HST metric. A rooted tree, as shown in Figure 1, is said to be an r-HST, or r-hierarchically well separated [START_REF] Pawan Kumar | On approximating arbitrary metrics by tree metrics[END_REF] if it satisfy the following properties: (i) all the leaf nodes are the labels; (ii) all edge weights are positive; (iii) the edge lengths from any node to all of its children are the same; and (iv) on any root to leaf path the edge weight decrease by a factor of at least r > 1. We can think of a r-HST as a hierarchical clustering of the given label set L. The root node is the cluster at the top level of the hierarchy and contains all the labels. As we go down in the hierarchy, the clusters break down into smaller clusters until we get as many leaf nodes as the number of labels in the given label set. The metric distance function defined on this tree d t (., .) is known as the r-HST metric. In other words, the distance d t (•, •) between any two nodes in the given r-HST is the length of the unique path between these nodes in the tree. The diameter diversity defined over d t (., .) is called the hierarchical P n Potts model. Figure 1 shows an example of diameter diversity defined over an r-HST.

The Hierarchical Move Making Algorithm

In the first part of this section we propose a move making algorithm for the hierarchical P n Potts model (defined in the previous section). In the second part, we show how our hierarchical move making algorithm can be used to address the general parsimonious labeling problem with optimality guarantees (strong multiplicative bound).

The Hierarchical Move Making Algorithm for the Hierarchical P n Potts Model

In the hierarchical P n Potts model the clique potentials are of the form of the diameter diversity defined over a given r-HST metric function. The move making algorithm proposed in this section to minimize such an energy function is a divide-and-conquer based approach, inspired by the work of [START_REF] Kumar | MAP estimation of semi-metric MRFs via hierarchical graph cuts[END_REF]. Instead of solving the actual problem, we divide the problem into smaller subproblems where each subproblem is a P n Potts model, which can be solved efficiently using α-expansion [START_REF] Kohli | P3 & beyond: Solving energies with higher order cliques[END_REF]. More precisely, given an r-HST, each node of the r-HST corresponds to a subproblem. We start with the bottom node of the r-HST, which is a leaf node, and go up in the hierarchy solving each subproblem associated with the nodes encountered.

In more detail, consider a node p of the given r-HST. Recall that any node p in the r-HST is a cluster of labels denoted as L p ⊆ L (Figure 1). In other words, the leaf nodes of the subtree rooted at p belongs to the subset L p . Thus, the subproblem defined at node p is to find the labeling x p where the label set is restricted to L p , as defined below.

x p = argmin

x∈(L p ) N i∈V θ i (x i ) + c∈C w c δ dia (Γ(x c )) . ( 7
)
If p is the root node, then the above problem (equation ( 7)) is as difficult as the original labeling problem (since L p = L). However, if p is the leaf node then the solution of the problem associated with p is trivial, x p i = p for all i ∈ V, that is, assign the label p to all the random variables. This insight leads to the design of our approximation algorithm, where we start by solving the simple problems corresponding to the leaf nodes, and use the labelings obtained to address the more difficult problem further up the Figure 2: An example of solving the labeling problem at non-leaf node (p) by combining the solutions of its child nodes {p 1 , p 2 }, given clique c and the labelings that it has obtained at the child nodes. The labeling fusion instance shown in this figure is the top two levels of the r-HST in the Figure 1. The diameter diversity of the labeling of clique c at node p 1 is 0 as it contains only one unique label l 1 . The diameter diversity of the labeling at p 2 is d t (l 3 , l 4 ) = 6 and at p is max {li,lj }∈{l1,l3,l4} d t (l i , l j ) = 18.

hierarchy. In what follows, we describe how the labeling of the problem associated with the node p, when p is a non-leaf node, is obtained using the labelings of its children node. Solving the Parent Labeling Problem. Before delving into the details, let us define some notations for the purpose of clarity. Let T be the depth (or the number of levels) of the given r-HST and N (τ ) be the set of nodes at level τ . The root node is at the top level (τ = 1). Let η(p) denotes the set of child nodes associated with a non-leaf node p and η(p, k) denotes its k th child node. Recall that our approach is bottom up. Therefore, for each child node of p we already have an associated labeling. We denote the labeling associated with the k th child of the node p as x η(p,k) . Thus, x η(p,k) i denotes the label assigned to the i th random variable by the labeling of the k th child of the node p. We also define an N dimensional vector t p ∈ {1, • • • , |η(p)|} N , where |η(p)| is the number of child nodes of node p. More precisely, for a given t p , t p i = k denotes that the label for the i th random variable comes from the k th child of the node p. Therefore, the labeling problem at node p reduces to finding the optimal t p . Thus, the labeling problem at node p amounts to finding the best child index k ∈ {1, • • • , |η(p)|} for each random variable i ∈ V so that the label assigned to the random variable comes from the labeling of the k th child (step 7, Algorithm 1).

Using the above notations, associated with a t p we define a new energy function as:

E(t p ) = i∈V θi (t p i ) + c∈C w c θc (t p c ). (8)
where

θi (t p i ) = θ i (x η(p,k) i ) if t p i = k. ( 9
)
Algorithm 1 The Move Making Algorithm for the Hierarchical P n Potts Model. input r-HST Metric; w c , ∀c ∈ C; and θ i (x i ), ∀i ∈ V 1: τ = T , the leaf nodes 2: repeat 3:

for each p ∈ N (τ ) do x p i = p, ∀i ∈ V Fusion Move tp = argmin

t p ∈{1,••• ,|η(p)|} N E(t p ) ( 10
)
8: In other words, the unary potential for t p i = k is the unary potential associated to the i th random variable corresponding to the label x η(p,k) i . The new clique potential θc (t p c ) is as defined below:

x p i = x η(p, tp i ) i
θc (t p c ) = γ p k , if t p i = k, ∀i ∈ c, γ p max , otherwise, (11)
where

γ p k = δ dia (Γ(x η(p,k) c
)) is the diameter diversity of the set of unique labels associated with x η(p,k) c and γ p max = δ dia ( Lp ). The set Lp = ∪ k∈η(p) Γ(x

η(p,k) c
) is the union of the unique labels associated with the child nodes of p. Recall that, because of the construction of the r-HST, L q ⊂ Lp ⊆ L p for all q ∈ η(p). Hence, the monotonicity property of the diameter diversity (Definition 1) ensures that γ p max > γ p k , ∀k ∈ η(p). This is the sufficient criterion to prove that the potential function defined by equation ( 11) is a P n Potts model. Therefore, the α-expansion algorithm can be used to obtain the locally optimal t p for the energy function [START_REF] Delong | Fast approximate energy minimization with label costs[END_REF]. Given the locally optimal tp , the labeling x p at node p can be trivially obtained as follows:

x p i = x η(p, tp i ) i .
In other words, the final label of the i th random variable is the one assigned to it by the ( tp i ) th child of node p. Figure 2 shows an instance of the above mentioned algorithm to combine the labelings of the child nodes to obtain the labeling of the parent node. The complete hierarchical move making algorithm for the hierarchical P n Potts model is shown in the Algorithm 1.

Multiplicative Bound. Theorem 1 gives the multiplicative bound for the move making algorithm for the hierarchical P n Potts model. Use the hierarchical move making algorithm defined in the Algorithm 1.

4:

Compute the corresponding energy. Proof Sketch. The factor of min(M, |L|) comes from the fact that each subproblem amounts to solving α-expansion for the P n Potts models. The factor of r r-1 comes from the fact that the edge lengths of the r-HST forms a geometric progression (refer to Figure 1), therefore, the distance between any two leaf node is upperbounded by e max r r-1 , where e max is the length of the longest edge. Please see the technical report for the detailed proof.

The Move Making Algorithm for the Parsimonious Labeling

In the previous subsection, we proposed a hierarchical move making algorithm for the hierarchical P n Potts model (Algorithm 1). This restricted us to a small class of clique potentials. In this section we generalize our approach to the much more general parsimonious labeling problem.

The move making algorithm for the parsimonious labeling problem is shown in Algorithm 2. Given diversity based clique potentials, non-negative clique weights, and arbitrary unary potentials, Algorithm 2 approximates the diversity into a mixture of hierarchical P n Potts models (using Al-gorithm 3) and then use the previously defined Algorithm 1 on each of the hierarchical P n Potts models.

The algorithm for approximating a given diversity into a mixture of hierarchical P n Potts models is shown in Algorithm 3. The first and the third steps of the Algorithm 3 have already been discussed in the previous sections. The second step, which amounts to finding the mixture of r-HST metrics for a given metric, can be solved using the randomized algorithm proposed in [START_REF] Fakcharoenphol | A tight bound on approximating arbitrary metrics by tree metrics[END_REF]. We refer the reader to [START_REF] Fakcharoenphol | A tight bound on approximating arbitrary metrics by tree metrics[END_REF] for further details of the algorithm for approximating a metric using a mixture of r-HST metrics.

Multiplicative Bound. Theorem 2 gives the multiplicative bound for the parsimonious labeling problem, when the clique potentials are any general diversity. Notice that the multiplicative bound of our algorithm is significantly better than the multiplicative bound of SoSPD [START_REF] Fix | A primal-dual algorithm for higher-order multilabel markov random fields[END_REF], which is M maxc δ(Γ(xc) minc δ(Γ(xc) . Theorem 2. The move making algorithm defined in Algorithm 2 gives the multiplicative bound of 4)). Here, M is the size of the largest maximal-clique and |L| is the number of labels.

Proof Sketch. The additional factor of (|L| -1) and O(log |L|) comes from the inequalities δ(L) ≤ (|L| -1)δ dia (L) [START_REF] Bryant | Diversities and the geometry of hypergraphs[END_REF] and d(., .) ≤ O(log |L|)d t (., .) [START_REF] Fakcharoenphol | A tight bound on approximating arbitrary metrics by tree metrics[END_REF], respectively. Technical report contains the detailed proof. Time Complexity. Each expansion move of our Algorithm 2 amounts to solving a graph-cut on a graph with 2|C| auxiliary variables and |C|(2M + 2) edges (in worst case), therefore, the time complexity is O((|V| + |C|) 2 |C|M). In addition, each subproblem in our algorithm is defined over a much smaller label set (number of child nodes). Furthermore, Algorithm 2 can be parallelized over the trees and over the subproblems at any level of the hierarchy. In contrast, each expansion move of SoSPD [START_REF] Fix | A primal-dual algorithm for higher-order multilabel markov random fields[END_REF] amounts to solving submodular max-flow, which is O(|V| 2 |C|2 M ) [START_REF] Fix | Structured learning of sum-of-submodular higher order energy functions[END_REF], exponential in the size of the largest clique. Furthermore, each expansion move of Ladicky et al. [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] amounts to solving a graph-cut on a graph with |C||L| auxiliary nodes and |C|(2M + |L|) edges having a time complexity of O((|V| + |C||L|) 2 |C|(M + |L|)) [START_REF] Goldberg | Maximum flows by incremental breadth-first search[END_REF]. As can be seen from the above discussion, our move-making algorithm is significantly more efficient for the parsimonious labeling problem.

Experiments

We demonstrate the utility of parsimonious labeling on both synthetic and real data. In the case of synthetic data, we perform experiments on a large number of grid lattices and evaluate our method based on the energy and the time taken. We show the modeling capabilities of the parsimonious labeling by applying it on two challenging real problems: (i) stereo matching, and (ii) image inpainting. We use the move-making algorithm for the co-occurrence based energy function proposed by Ladicky et al. [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] as our baseline. Based on the synthetic and the real data results, supported by the theoretical guarantees, we show that the move making algorithm proposed in our work outperforms [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF].

Recall that the energy function we are interested in minimizing is defined in the equation [START_REF] Bryant | Diversities and the geometry of hypergraphs[END_REF]. In our experiments, we frequently use the truncated linear metric. We define it below for the sake of completeness.

θ i,j (l a , l b ) = λ min(|l a -l b |, M ), ∀l a , l b ∈ L. ( 12
)
where λ is the weight associated with the metric and M is the truncation constant.

Synthetic Data

We consider following two cases: (i) given the hierarchical P n Potts model, and (ii) given a general diversity based clique potential. In each of the two cases, we generate lattices of size 100 × 100, 20 labels, and use λ = 1. The cliques are generated using a window of size 10 × 10 in a sliding window fashion. The unary potentials are randomly sampled from the uniform distribution defined over the interval [0, 100]. In the first case, we randomly generate 100 lattices and random r-HST trees associated with each lattice, ensuring that they satisfy the properties of the r-HST. Each r-HST is then converted into hierarchical P n Potts model by defining diameter diversity over each of them. The hierarchical P n Potts model is then used as the actual clique potential. We performed 100 such experiments. On the other hand, in the second case, for a given value of the truncation M , we generate a truncated linear metric and 100 lattices. We treat this metric as the induced metric of a diameter diversity and apply Algorithm 1 for the energy minimization. We used four different values of the truncation factor M ∈ {1, 5, 10, 20}. For both the experiments, we used 7 different values of w c : w c ∈ {0, 1, 2, 3, 4, 5, 100}.

The average energy and the time taken for both the methods and both the cases are shown in the Figure 3. It is evident from the figures that our method outperforms [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] both in terms of time and the energy. In case (ii), despite the fact that our method first approximates the given diversity into mixture of hierarchical P n Potts models, it outperforms [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF]. This can be best supported by the fact that our algorithm has a strong multiplicative bound.

Real Data

In case of real data, the high-order cliques are the superpixels obtained using the mean-shift method [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF], the clique potentials are the diameter diversity of the truncated linear metric (equation ( 12)). A truncated linear metric enforces smoothness in the pairwise setting, therefore, its diameter diversity will naturally enforce smoothness in the high-order cliques, which is a desired cue for the two applications we are dealing with. In both the real experiments we use w c = exp -ρ(xc ) σ 2 (for high order cliques), where ρ(x c ) is the variance of the intensities of the pixels in the clique x c and σ is a hyperparameter.

Stereo Matching

Given two rectified stereo pair of images, the problem of stereo matching is to find the disparity (gives the notion of depth) of each pixel in the reference image [START_REF] Szeliski | A comparative study of energy minimization methods for markov random fields with smoothness-based priors[END_REF][START_REF] Tappen | Comparison of graph cuts with belief propagation for stereo, using identical mrf parameters[END_REF]. We extend the standard setting of the stereo matching [START_REF] Szeliski | A comparative study of energy minimization methods for markov random fields with smoothness-based priors[END_REF] to highorder cliques and test our method to the images, 'tsukuba' and 'teddy', from the widely used Middlebury stereo data set [START_REF] Scharstein | A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[END_REF]. The unaries are the L1-norm of the difference in the RGB values of the left and the right image pixels. Notice that the index for the right image pixel is the index for the left image pixel minus the disparity, where disparity is the label. For 'tsukuba' and 'teddy' we used 16 and 60 labels respectively. In case of 'teddy' the unaries are trucated at 16. The weights w c for the pairwise cliques are set to be proportional to the L1-norm of the gradient of the intensities of the neighboring pixels ∇ 1 . In case of 'tsukuba', if ∇ 1 < 8, w c = 2, otherwise w c = 1. In case of 'teddy', if ∇ 1 < 10, w c = 3, otherwise w c = 1. As mentioned earlier, w c for the high-order cliques is set to be proportional to the variance. We used different values of σ, λ, and M . Because of the space constraints we are showing results for the following setting: for 'tsukuba', λ = 20, σ = 100, and M = 5; for 'teddy', λ = 20, σ = 100, and M = 1. Figure 4 shows the results obtained. Notice that our method significantly outperforms [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] in terms of energy and the visual quality for both 'tsukuba' and 'teddy'.

Image Inpainting and Denoising

Given an image with added noise and obscured regions (regions with missing pixels), the problem is to denoise the image and fill the obscured regions such that it is consistent with the surroundings. We perform this experiment on the images, 'penguin' and 'house', from the widely used Middlebury data set. The images under consideration are gray scale, therefore, there are 256 labels in the interval [0, 255], each representing an intensity value. The unaries for each pixel (or node) corresponding to a particular label is the squared difference between the label and the intensity value at that pixel. The weights w c for the pairwise cliques are all set to one. We used different values of σ, λ, and the truncation M . Because of the space constraints we are showing results for the following setting: 'penguin', the λ = 40, σ = 10000 and M = 40; for 'house', the λ = 50, σ = 1000 and M = 50. Notice that our method (Figure 5) significantly outperforms [START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] in terms of energy and visual quality for both 'penguin' and 'house'.

Discussion

We proposed a new family of labeling problems, called parsimonious labeling, where the energy function is defined using a diversity measure. Our energy function includes the Visually, our method gives much more appealing results. We use super-pixels obtained using the mean-shift as the cliques.

novel hierarchical P n Potts model, which allows us to design an efficient and accurate move-making algorithm based on iteratively solving the minimum st-cut problem.

The large class of energy functions covered by parsimonious labeling can be used for various computer vision tasks such as semantic segmentation (where diversity function can be used to favor certain subsets of semantic classes), or 3D reconstruction (where diversity function can be used to favor certain subsets of depth values).

An interesting direction for future research would be to explore different diversities and propose specific algorithms for them, which may provide better theoretical guarantees. Another interesting work would be to directly approximate diversities into a mixture of hierarchical P n Potts model, without the use of the intermediate r-HST metrics. This may also lead to better multiplicative bounds.

4 :

 4 if |η(p)| = 0, leaf node then 5:

τ

  ← τ -1 12: until τ > 0.

Algorithm 2

 2 The Move Making Algorithm for the Parsimonious Labeling Problem. input Diversity (L, δ); w c , ∀c ∈ C; θ i (x i ), ∀i ∈ V; L; k 1: Approximate the given diversity as the mixture of k hierarchical P n Potts model using Algorithm 3. 2: for each hierarchical P n Potts model in the mixture do 3:

4 :

 4 Obtain the corresponding hierarchical P n Potts model by defining the diameter diversity over d t (., .) 5: end for Theorem 1. The move making algorithm for the hierarchical P n Potts model, Algorithm 1, gives the multiplicative bound of r r-1 min(M, |L|) with respect to the global minima. Here, M is the size of the largest maximal-clique and |L| is the number of labels.

  r r-1 (|L| -1)O(log |L|) min(M, |L|) for the parsimonious labeling problem (equation (

Figure 3 :

 3 Figure 3: Synthetic (Blue: Our, Red: Co-occ [22]). The x-axis of all the figures is the weight associated with the cliques (w c ). Figures (a) and (b) are the plots when the hierarchical P n Potts model is known. Figures(c) and (d) are the plots when a diversity (diameter diversity over truncated linear metric) is given as the clique potentials which is then approximated using the mixture of hierarchical P n Potts model. Notice that in both the cases our method outperforms the baseline[START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] both in terms of energy and time. Also, for very high value of w c = 100, both the methods converges to the same labeling. This is expected as a very high value of w c enforces rigid smoothness by assigning everything to the same label.

  (a) Tsukuba (Energy, Time (sec)) (b) Our (1387300, 773) (c) Co-occ [22] (2117804, 306) (d) Teddy (Energy, Time (sec)) (e) Our (3196400, 2918) (f) Co-occ [22] (3256200, 1392)

Figure 4 :

 4 Figure 4: Stereo Matching Results. Figures (a) and (d) are the ground truth disparity for the 'tsukuba' and 'teddy' respectively. Our method significantly outperforms the baseline Co-ooc [22] in both the cases in terms of energy. Our results are visually more appealing also. Figures (b) and (e) clearly shows the influence of 'parsimonious labeling' as the regions are smooth and the discontinuity is preserved. Recall that we use super-pixels obtained using the mean-shift as the cliques.

Figure 5 :

 5 Figure 5: Image inpainting results. Figures (a) and (d) are the input images of 'penguin' and 'house' with added noise and obscured regions. Our method, (b) and (e), significantly outperforms the baseline[START_REF] Ladicky | Graph cut based inference with co-occurrence statistics[END_REF] in both the cases in terms of energy. Visually, our method gives much more appealing results. We use super-pixels obtained using the mean-shift as the cliques.

  5: end for 6: Choose the solution with the minimum energy.

	Algorithm 3 Diversity to Mixture of Hierarchical P n Potts
	Model.
	input Diversity (L, δ), k

1: Compute the induced metric, d(., .), where d(l i , l j ) = δ({l i , l j }), ∀l i , l j ∈ L. 2: Approximate d(., .) into mixture of k r-HST metrics d t (., .) using the algorithm proposed in

[START_REF] Fakcharoenphol | A tight bound on approximating arbitrary metrics by tree metrics[END_REF]

. 3: for each r-HST metrics d t (., .) do

Acknowledgments. Puneet Dokania is partially funded by the European Community's Seventh Framework Programme under the ERC Grant agreement number 259112 and MOBOT Grant agreement number 600796, and Pôle de Compétitivité Medicen/ADOC Grant agreement number l11012185.