domain: info math

text:
Nikos Komodakis

Bo Xiang

Nikos Paragios

A Framework for Efficient Structured Max-Margin Learning of High-Order MRF Models *

Keywords: Markov Random Fields, Conditional Random Fields, structured prediction, parameter estimation, graphical models, convex optimization

We present a very general algorithm for structured prediction learning that is able to efficiently handle discrete MRFs/CRFs (including both pairwise and higher-order models) so long as they can admit a decomposition into tractable subproblems. At its core, it relies on a dual decomposition principle that has been recently employed in the task of MRF optimization. By properly combining such an approach with a max-margin learning method, the proposed framework manages to reduce the training of a complex high-order MRF to the parallel training of a series of simple slave MRFs that are much easier to handle. This leads to a very efficient and general learning scheme that relies on solid mathematical principles. We thoroughly analyze its theoretical properties, and also show that it can yield learning algorithms of increasing accuracy since it naturally allows a hierarchy of convex relaxations to be used for loss-augmented MAP-MRF inference within a max-margin learning approach. Furthermore, it can be easily adapted to take advantage of the special structure that may be present in a given class of MRFs. We demonstrate the generality and flexibility of our approach by testing it on a variety of scenarios, including training of pairwise and higher-order MRFs, training by using different types of regularizers and/or different types of dissimilarity loss functions, as well as by learning of appropriate models for a variety of vision tasks (including high-order models for compact pose-invariant shape priors, knowledge-based segmentation, image denoising, stereo matching as well as high-order Potts MRFs).

Un cadre efficace pour l'apprentissage structuré à marge maximale (SVM) de modèles de MRF d'ordres supérieurs

Résumé :

Nous présentons un algorithme très général pour l'apprentissage structuré capable de gérer des MRFs ou CRFs discrets (pouvant contenir des hyper-arêtes d'ordre supérieur) tant que ces derniers admettent une décomposition en sous-problèmes optimisables. Fondamentalement, l'algorithme utilise le principe de la décomposition duale qui a été employée récemment pour l'optimisation de MRF. En combinant intelligemment cette approche avec une méthode d'apprentissage à marge maximale, on arrive à réduire l'entraînement d'un MRF d'ordre supérieur à l'entraînement parallèle d'une série de sous-problèmes simples bien plus facile à gérer. Nous avons alors un cadre pour l'apprentissage général et très efficace, qui s'appuie sur des principes mathématiques solides. Nous étudierons en détails ses propriétés théoriques et montrerons que l'on peut obtenir des algorithmes d'apprentissage de plus en plus précis car il admet naturellement une hiérarchie de relaxations convexes utilisables pour l'inférence de MAP-MRF avec augmentation de la fonction de perte (loss-augmented inference), le tout dans une approche d'apprentissage à marge maximale. De plus, l'approche peut être facilement adaptée pour utiliser la structure particulière d'une classe de MRFs. Nous démontrerons la généralité et la flexibilité de notre approche en la testant sur une variété de scénarios dont l'entraînement de MRF d'ordre 1 puis supérieurs, l'entraînement avec différents types de régularisations et différents type de fonctions de perte, et l'apprentissage de modèles appropriés pour de nombreuses tâches concernant la vision (ordres supérieurs pour des aprioris de forme compacts et invariants par rapport à la pose, segmentation, débruitage d'images, appariement stéréo et MRFs avec des potentiels de Potts d'ordres supérieurs).

Mots-clés : Champs aléatoires de Markov, champs conditionnels aléatoires, prédiction structurée, estimation de paramètre, modèle graphique, optimisation convexe In MRF/CRF training, one aims to learn a mapping f : X → Y between a typically high-dimensional input space X and an output space of MRF/CRF variables Y . In stereo matching, for instance, the elements of the input space X correspond to stereoscopic images, and the elements of the output space Y correspond to disparity maps. (b) In general, the mapping f (x) is defined as minimizing the energy E G(u(y|w), h(y|w)) of an MRF/CRF model whose unary and higher-order potentials u(y|w), h(y|w) are parameterized by w (the potentials also depend on x, but this is omitted here to simplify notation). Therefore, to fully specify this mapping it suffices to estimate w, which is what parameter learning aims to achieve in this case. (c) Our framework reduces, in a principled manner, the training of a complex MRF model into the parallel training of a series of easy-to-handle slave MRFs. The latter can be freely chosen so as to fully exploit the problem structure, which, in addition to efficiency, contributes a sufficient amount of flexibility and generality to our method.

Introduction

Markov Random Fields (MRFs), and their discriminative counterparts Conditional Random Fields (CRFs)1 [START_REF] Lafferty | Conditional random fields: Probabilistic models for segmenting and labeling sequence data[END_REF], are ubiquitous in computer vision and image analysis [START_REF] Blake | Advances in Markov random fields for vision and image processing[END_REF][START_REF] Li | Markov Random Field Modeling in Image Analysis[END_REF]. They have been used with great success in a variety of applications so far, including both low-level and high-level problems from the above domains [START_REF] Glocker | Dense image registration through MRFs and efficient linear programming[END_REF][START_REF] Komodakis | Image completion using global optimization[END_REF][START_REF] Kumar | Learning specific-class segmentation from diverse data[END_REF][START_REF] Zhou | A map-estimation framework for blind deblurring using high-level edge priors[END_REF]. Due to this fact, algorithms that perform MAP estimation for models of this type have attracted a significant amount of research interest in the computer vision community over the past years [START_REF] Conejo | Inference by learning: Speeding-up graphical model optimization via a coarse-to-fine cascade of pruning classifier[END_REF][START_REF] Jörg | A comparative study of modern inference techniques for discrete energy minimization problem[END_REF][START_REF] Komodakis | Approximate labeling via graph-cuts based on linear programming[END_REF][START_REF] Kumar | Fast memory-efficient generalized belief propagation[END_REF][START_REF] Kumar | Efficiently solving convex relaxations for map estimation[END_REF][START_REF] Szeliski | A comparative study of energy minimization methods for markov random fields with smoothness-based priors[END_REF]. However, besides the ability to accurately minimize the energy of a MRF model, another extremely crucial issue is how to actually select this energy in the first place, such that the resulting model yields an accurate representation of a specific problem that one aims to solve (a MAP-MRF solution is of little value if the used MRF model does not properly represent the problem at hand). It turns out that one of the most successful and principled ways for achieving this goal is through learning. In such a context, one proceeds by parameterizing the potentials of a MRF model by a vector of parameters w, and, then, these parameters are estimated automatically by making use of training data that are given as input. For many cases in vision, this is, in fact, the only viable solution as the existing parameters can often be too many to tune by hand ( e.g., deformable parts-based models for object detection can have thousands of parameters to estimate). As a result, learning algorithms for MRF parameter estimation play a fundamental role in successfully applying MRF models to computer vision problems. However, training these models poses a task that is quite challenging. This is because, unlike standard machine learning tasks where one must learn functions predicting simple true-false answers or scalar values (as in classification and regression), the goal, in this case, is to learn models that predict answers much more complex consisting of multiple interrelated variables. In fact, this is a characteristic example of what is known as structured prediction learning, where one uses a set of input-output training pairs (x k , y k )

1≤k≤K ⊆ X ×Y to estimate a function f : X → Y that has the following characteristics: both the input and output spaces X, Y are high-dimensional, and, furthermore, the variables in Y are interrelated, i.e., each element y ∈ Y carries out some structure (for instance, it can represent a graph). In the particular case of MRF parameter estimation, X is representing the space where the observations (e.g., the input visual data) reside, whereas Y is representing the space of the variables of the MRF model (see Fig. 1(a), 1(b)).

In fact, the difficulty of the above task becomes even greater due to the computational challenges that are often raised by computer vision applications with regard to learning. For instance, many of the MRFs used in vision are of large scale. Also, the complexity and diversity of vision tasks often require the training of MRFs with complex potential functions. On top of that, over the last years the use of high order MRFs is becoming increasingly popular in vision since such MRFs are often found to considerably improve the quality of estimated solutions. Yet, most of the MRF learning methods proposed in the vision literature so far focus mainly on models with pairwise potentials or on specific classes of high-order models for which they need to derive specifically tailored algorithms [START_REF] Alahari | Efficient piecewise learning for conditional random fields[END_REF][START_REF] Anguelov | Discriminative learning of markov random fields for segmentation of 3d scan data[END_REF][START_REF] Kumar | Exploiting inference for approximate parameter learning in discriminative fields: An empirical study[END_REF][START_REF] Meshi | Learning efficiently with approximate inference via dual losses[END_REF][START_REF] Daniel Munoz | Contextual classification with functional max-margin markov networks[END_REF][START_REF] Scharstein | Learning conditional random fields for stereo[END_REF][START_REF] Szummer | Learning CRFs using graph cuts[END_REF].

The goal of this work is to address the above mentioned challenges by proposing a general learning method that can be directly applicable to a very broad class of problems. To achieve this goal the proposed method makes use of some recent advances made on the MRF optimization side [START_REF] Komodakis | MRF optimization via dual decomposition: Message-passing revisited[END_REF][START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF], which it combines with a max-margin approach for learning [START_REF] Taskar | Max-margin markov networks[END_REF]. More specifically, it makes use of a dual decomposition approach [START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF] that has been previously used for MAP estimation. Thanks to this approach, it essentially manages to reduce the task of training a complex MRF to that of training in parallel a series of simpler slave MRFs that are much easier to handle within a max-margin framework (Fig. 1(c)). The concurrent training of the slave MRFs takes place in a principled way through an efficient projected subgradient algorithm. This leads to a powerful learning framework that makes the following contributions compared to prior art:

1. It is able to efficiently handle not just pairwise log-linear MRF models but also high-order ones as long as the latter can admit a decomposition into tractable subproblems, in which case no other restriction needs to be imposed on the topology of the underlying MRF graph or on the type of MRF potentials.

2. Thanks to the parallel training of a series of easy-to-handle submodels in combination with the used projected subgradient method, it leads to a highly efficient learning scheme that is scalable even to very large problems. Moreover, unlike prior cutting-plane or primal subgradient descent methods for max-margin learning, which require performing loss-augmented MAP-MRF inference to completion at every iteration, the proposed scheme is able to jointly optimize both the vector of parameters and the loss-augmented MRF inference variables.

3. It allows a hierarchy of convex relaxations for MAP-MRF estimation to be used in the context of learning for structured prediction (where this hierarchy includes all the commonly used LP relaxations for MRF inference), thus leading to structured prediction learning algorithms of increasing accuracy.

4. It is sufficiently flexible and extendable, as it only requires providing a routine that computes an optimizer for the slave MRFs. As a result, it can be easily adapted to take advantage of the special structure that may exist in a given class of MRF models to be trained.

Inria

The present paper is based on our previous work [START_REF] Komodakis | Efficient training for pairwise or higher order CRFs via dual decomposition[END_REF]. Compared to that work, here we also provide a more detailed mathematical and theoretical analysis of our method as well as a significantly extended set of experimental results, including results for learning pose invariant models, for knowledge-basesd segmentation (both on 2D and 3D cases), for training using high-order loss functions, as well as for training using sparsity inducing regularizers.

Related work

Over the past years, structured prediction learning has been a topic that has attracted a significant amount of interest both from the vision and machine learning community. There is, therefore, a substantial body of related work in this area. Many approaches on this topic can essentially be derived from, or are based on, the socalled regularized risk minimization paradigm, where one is given a set of training samples (x k , y k ) 1≤k≤K ⊆ X × Y (assumed to be generated by some unknown distribution on X × Y ) and seeks to estimate the parameters w of a graphical model, such as a Markov Random Field, by minimizing an objective function of the following form

min w R(w) + C K k=1 L(y k , y k (x k |w)) . (1)
In the above, y k denotes the desired (i.e., ground truth) MRF labeling of the k-th training sample, y k (x k |w) denotes the corresponding labeling that results from minimizing an MRF instance constructed from the input x k and parameterized by w, and L(•, •) is a loss function used for incurring a penalty if there exist differences between the two solutions y k and y k (x k |w).

In view of this notation, the second term in (1) represents essentially an empirical risk that is used for approximating the true risk, which cannot be computed due to the fact that the joint distribution on the input-output pairs (x, y) ∈ X × Y is not known. The above approximation of the true risk is equal to the average of the loss on the input training samples, which is combined in (1) with a regularizer R(w), whose main role is essentially to prevent overfitting (the relative importance of the two terms, i.e., the regularizer and the empirical risk, is determined by the regularization constant C in (1)). Depending on the choice made for the loss function L(•, •), different types of structured prediction learning methods can be recovered, including both generative (e.g., maximum-likelihood) and discriminative (e.g., max-margin) algorithms, which comprise the two most general and widely used learning approaches. In the case of maximum-likelihood learning, one maximizes (possibly along with an L2 norm regularization term) the product of posterior probabilities of the ground truth MRF labelings k P (y k |w), where P (y|w) ∝ exp -E(y|w) denotes the probability distribution induced by an MRF model with energy E(y|w). This leads to a convex differentiable objective function that can be optimized using gradient ascent. However, in the case of log-linear models, it is known that computing the gradient of this function involves taking expectations (of some appropriate feature functions) with respect to the MRF distribution P (y|w). This, therefore, requires performing probabilistic MRF inference, which is, in general, an intractable task. As a result, approximate inference techniques (such as the loopy belief propagation algorithm [START_REF] Murphy | Loopy-belief propagation for approximate inference: An empirical study[END_REF]) are often used for approximating the MRF marginals required for the estimation of the gradient. This is, e.g., the case in [START_REF] Scharstein | Learning conditional random fields for stereo[END_REF], where the authors demonstrate how to train a CRF model for stereo matching, as well as in [START_REF] Kumar | Exploiting inference for approximate parameter learning in discriminative fields: An empirical study[END_REF], where a comparison with other MRF training methods such as the pseudo-likelihood [START_REF] Besag | Efficiency of pseudolikelihood estimation for simple Gaussian fields[END_REF], [START_REF] Kumar | Discriminative random fields[END_REF] and MCMC-based contrastive divergence [START_REF] Hinton | Training products of experts by minimizing contrastive divergence[END_REF] are included as well. A disadvantage, of course, of having to use approximate probabilistic inference techniques is that the estimation of the gradient is incorrect and so it is difficult for these methods to provide any theoretical guarantees.

Besides maximum-likelihood, another widely used class of structured prediction learning techniques, the so-called max-margin learning methods, can be derived from ( 1) by choosing a hingeloss term as the loss function L(•, •). In this case, it turns out that the goal of the resulting optimization problem is to adjust the MRF parameters w so that, ideally, there is at least a non-negative margin attained between the energy attained by the ground truth solution of a training sample and the energy of any other solution.

When R(w) = ||w|| 2 , such a problem is equivalent to a convex quadratic program (QP) with an exponential number of linear inequality constraints. One class of methods [START_REF] Finley | Training structural svms when exact inference is intractable[END_REF][START_REF] Li | Learning for stereo vision using the structured support vector machine[END_REF][START_REF] Yadollahpour | DivMCuts: Faster Training of Structural SVMs with Diverse M-Best Cutting-Planes[END_REF] try to solve this QP by use of a cutting-plane approach. These methods rely on the core idea that only a very small fraction of the exponentially many constraints will actually be active at an optimal solution. Therefore, they proceed by solving a small QP whose number of constraints increases at each iteration. The increase, in this case, takes place by finding and adding the most violated constraints each time (still, the total number of constraints can be shown to be polynomially upper-bounded). However, one drawback of such an approach relates to the fact that computing the most violated constraint requires solving at each iteration a loss-augmented MAP-MRF inference problem that is, in general, NP-hard. Therefore, one still has to resort to approximate MAP inference techniques. This can lead to the so-called under-generating or overgenerating approaches depending on the type of approximate inference used during this step. The former approaches rely on algorithms that consider only a subset of all possible solutions for the loss-augmented MAP-MRF inference step. As a consequence, solutions that are not considered do not get penalized during training. In contrast, the latter approaches make use of algorithms that consider a superset of the valid solutions. This typically means also penalizing fractional solutions corresponding to a relaxation of the loss-augmented MAP-MRF inference problem, thus promoting the extraction of a valid integral solution at test time. Due to this fact, overgenerating approaches are typically found to have much better empirical performance [START_REF] Finley | Training structural svms when exact inference is intractable[END_REF].

Crucially, however, both undergenerating and overgenerating approaches typically impose great computational cost during training, especially for problems of large scale or high order that are frequently encountered in computer vision, due to the fact that the MAP inference process has to be performed at the level of full size MRFs at each iteration. Note that this a very important issue that appears in other existing methods as well, e.g., [START_REF] Ratliff | online) subgradient methods for structured prediction[END_REF]. An exception perhaps is the special case of submodular MRFs, for which the authors of [START_REF] Anguelov | Discriminative learning of markov random fields for segmentation of 3d scan data[END_REF] have shown how to express the exponential set of constraints in a compact form, thus allowing for a more efficient MRF training to take place under this setting.

The method proposed in this paper aims to address the aforementioned shortcomings. It belongs to the class of overgenerating training methods. Among other methods of this type, the approach closest to our work is [START_REF] Meshi | Learning efficiently with approximate inference via dual losses[END_REF], where the authors choose to replace the structured hinge-loss for pairwise MRFs by a convex dual upper bound that decomposes over the MRF cliques (the specific dual bound that has been used in this case is the one that was first employed in the context of the max-sum diffusion algorithm [START_REF] Werner | A linear programming approach to max-sum problem: A review[END_REF]). That work, however, focuses on the training of pairwise MRFs, but it can potentially be extended to higher-order models by properly adapting the dual bound of [START_REF] Werner | A linear programming approach to max-sum problem: A review[END_REF] and deriving corresponding block-coordinate dual ascent methods. Our method, on the other hand, handles directly in a unified, elegant and modular manner high-order models, models that employ tighter relaxations for improved accuracy, higher-order loss functions, as well as models with any type of special characteristics (e.g., submodularity). Furthermore, [START_REF] Meshi | Learning efficiently with approximate inference via dual losses[END_REF] is theoretically valid, and thus applicable, only to problems with a strictly convex regularizer such as the squared l 2 -norm. In contrast, our approach handles any convex regularizer (including ones based on sparsity inducing norms -e.g., l 1 -that have often proved to be very useful Inria during learning), offering guaranteed convergence in all cases. Moreover, an additional advantage compared to [START_REF] Meshi | Learning efficiently with approximate inference via dual losses[END_REF] is that our method is parallelizable, as it allows all of the optimizers for the slave MRFs to be computed concurrently (instead of sequentially). One other max-margin training method that replaces the loss-augmented inference step by a compact dual LP relaxation is the approach proposed in [START_REF] Franc | Discriminative learning of max-sum classifiers[END_REF] . However, this is done only for a restricted class of MRF problems (those with a strictly trivial equivalent), for which the LP relaxation is assumed to be equivalent to the original MRF optimization. An additional CRF learning method that makes use of duality is [START_REF] Hazan | A primal-dual message-passing algorithm for approximated large scale structured prediction[END_REF], which proposes an approximation for the CRF structured-prediction problem based on a local entropy approximation and derives an efficient message-passing algorithm with guaranteed convergence. Similarly to our method and [START_REF] Meshi | Learning efficiently with approximate inference via dual losses[END_REF], the method proposed in [START_REF] Hazan | A primal-dual message-passing algorithm for approximated large scale structured prediction[END_REF] breaks down the classical separation between inference and learning, and tries to directly formulate the learning problem via message passing operations, but uses different dual formulations and optimization techniques.

It should be mentioned at this point that, over the last years, additional types of structured prediction training methods have been proposed that can make use of various other types of learning objective functions and losses, as well as optimization algorithms [START_REF] Domke | Learning graphical model parameters with approximate marginal inference[END_REF][START_REF] Gould | Max-margin learning for lower linear envelope potentials in binary mrfs[END_REF][START_REF] Mcallester | Direct loss minimization for structured prediction[END_REF][START_REF] Miller | Max-margin min-entropy models[END_REF][START_REF] Miller | Max-margin min-entropy models[END_REF][START_REF] Nowozin | Decision tree fields[END_REF][START_REF] Park | On learning higher-order consistency potentials for multi-class pixel labeling[END_REF][START_REF] Pletscher | Learning low-order models for enforcing high-order statistics[END_REF][START_REF] Tappen | The logistic random field -a convenient graphical model for learning parameters for mrf-based labeling[END_REF][START_REF] Tarlow | Structured output learning with high order loss functions[END_REF]. This also includes recent cases such as the inference-machines framework proposed in [START_REF] Daniel Munoz | Stacked hierarchical labeling[END_REF], as well as various types of randomized models such as the "Perturb-and-MAP" framework [START_REF] Papandreou | Perturb-and-map random fields: Using discrete optimization to learn and sample from energy models[END_REF] or the "randomized optimum models" described in [START_REF] Tarlow | Randomized optimum models for structured prediction[END_REF]. Also, a pseudo-max approach to structured learning (inspired by the pseudo-likelihood method) is proposed in [START_REF] Sontag | More data means less inference: A pseudo-max approach to structured learning[END_REF], where the authors also analyze for which cases such an approach leads to consistent training. Furthermore, learning algorithms that can handle graphical models with hidden variables have been recently proposed as well, in which case it is assumed that only partial ground truth labelings are given as input during training [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF][START_REF] Komodakis | Learning to cluster using high order graphical models with latent variables[END_REF][START_REF] Kumar | Modeling latent variable uncertainty for loss-based learning[END_REF][START_REF] Schwing | Efficient structured prediction with latent variables for general graphical models[END_REF][START_REF] Yu | Learning structural SVMs with latent variables[END_REF]. Last, but not least, another strand of work focuses on developing learning approaches for the case of continuously valued MRF problems [START_REF] Kegan | Learning optimized map estimates in continuously-valued mrf models[END_REF].

The remainder of this paper is structured as follows. We begin by briefly reviewing the dual decomposition method for MAP estimation in §3. We also review the max-margin structured prediction approach in §4. We describe in detail our MRF learning framework and also thoroughly analyze various aspects of it in §5- §7. We show experimental results for a variety of different settings and tasks in §8. Finally, we present our conclusions in §9.

MRF Optimization via Dual Decomposition

Let L denote a discrete label set, and let G = (V, C) be a hypergraph consisting of a set of nodes V and a set of hyperedges2 C. A discrete MRF defined on the hypergraph G is specified by its so-called unary and higher-order potential functions u = u p p∈V and h = h c c∈C respectively (where, for every p ∈ V and c ∈ C, u p : L → R and h c :

L |c| → R). If y = y p p∈V ∈ L |V| represents a labeling of the nodes in V, the values u(y) = u p (y p )
p∈V and h(y) = h c (y c ) c∈C of the above potential functions (where y c denotes the set y p |p ∈ c ) define the MRF energy of y as

E G (u(y), h(y)) := p∈V u p (y p ) + c∈C h c (y c ) . (2)
In MRF optimization the goal is to find a labeling y that attains the minimum of the above energy function, which amounts to solving the following task

min y∈L |V| E G (u(y), h(y)) . (3)
The above problem is, in general, NP-hard. One common way to compute approximately optimal solutions to it is by making use of convex relaxations. The dual decomposition framework in [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF][START_REF] Komodakis | Towards more efficient and effective lp-based algorithms for mrf optimization[END_REF][START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF] provides a very general and flexible method for deriving and solving tight dual relaxations in this case. According to this framework, a set

G i = (V i , C i ) 1≤i≤N of sub-hypergraphs of the original hypergraph G = (V, C) is first chosen such that V = ∪ N i=1 V i , C = ∪ N i=1 C i .
The original hard optimization problem min y E G (u(y), h(y)) (also called the master ) is then decomposed into a set of easier to solve subproblems min y E Gi (u i (y), h(y))

1≤i≤N (called the slaves), which involve optimizing local MRFs defined on the chosen sub-hypergraphs G i 1≤i≤N . As can be seen, each slave MRF inherits3 the higher-order potentials h of the master MRF, but has its own unary potentials u i = u i p p∈Vi . Its energy function is thus given by

E G i (u i (y), h(y)) := p∈V i u i p (y p ) + c∈C i h c (y c ) .
The condition that the above unary potentials u i have to satisfy is the following

i∈Ip u i p = u p , ∀p ∈ V , (4)
where I p denotes the set of indices of all sub-hypergraphs containing node p, i.e.,

I p = {i|p ∈ V i } . (5)
The above property simply expresses the fact that the sum of the unary potentials of the slaves should give back the unary potentials of the master MRF. Due to this property, the sum of the minimum energies of the slaves can be shown to always provide a lower bound to the minimum energy of the master MRF, i.e., it holds

N i=1 min y E G i (u i (y), h(y)) ≤ min y E G (u(y), h(y)) . (6)
Maximizing the lower bound appearing on the left-hand side of ( 6) by adjusting the unary potentials u i 1≤i≤N (which play the role of dual variables in this case) gives rise to the following dual relaxation for problem (3)

DUAL Gi (u, h) = max {u i } 1≤i≤N N i=1 min y E Gi (u i (y), h(y)) (7)
s.t.

i∈Ip u i p = u p , (∀p ∈ V) . (8)
By simply choosing different decompositions G i 1≤i≤N of the hypergraph G, one can derive different convex relaxations to problem (3). These include the standard marginal polytope LP relaxation for pairwise MRFs, which is widely used in practice, as well as alternative relaxations that can be much tighter4 .

Max-margin Markov Networks

Let us now return to the central topic of the paper, which is the training of MRF/CRF models.

To that end, let x k , y k 1≤k≤K ∈ X × Y be a training set of K samples, where x k , y k represent the input observations and the label assignments of the k-th sample, respectively. We assume that the MRF instance associated with the k-th sample is defined on a hypergraph5 G = (V, C), and both the unary potentials u k = u k p p∈V and the higher-order potentials h k = h k c c∈C of that MRF are parameterized linearly in terms of a vector of parameters w we seek to estimate, i.e.,

u k p (y p |w) = w T • φ p (y p , x k ), h k c (y c |w) = w T • φ c (y c , x k ) , (9)
where φ p (•, •), φ c (•, •) represent known vector-valued feature functions that are extracted from the corresponding observations x k (and are application-specific). Note that, by properly zeropadding these vector-valued features φ p (•, •) and φ c (•, •), the above formulation allows us to use separate parameters for each different node, clique or even label 6 . Let ∆(y, y ) represents a dissimilarity measure between any two MRF labelings y and y (that satisfies ∆(y, y ) ≥ 0 and ∆(y, y) = 0). In a maximum margin Markov network [START_REF] Taskar | Max-margin markov networks[END_REF] one ideally seeks a vector of parameters w such that the MRF energy of the desired ground-truth solution y k is smaller by a margin ∆(y, y k ) than the MRF energy of any other solution y, i.e.,

(∀y), E G (u k (y k |w), h k (y k |w)) ≤ E G (u k (y|w), h k (y|w)) -∆(y, y k ) . ( 10
)
To account for the fact that there might be no vector w satisfying all of the above constraints, a slack variable ξ k per sample is introduced that allows some of the constraints to be violated

(∀y), E G (u k (y k |w), h k (y k |w)) ≤ E G (u k (y|w), h k (y|w)) -∆(y, y k ) + ξ k . (11)
Ideally, ξ k should take a zero value. In general, however, it can hold ξ k > 0 and so the goal, in this case, is to adjust w such that the sum K k=1 ξ k (which represents the total violation of constraints [START_REF] Domke | Learning graphical model parameters with approximate marginal inference[END_REF]) takes a value that is as small as possible. This leads to solving the following constrained minimization problem, where a regularization term R(w) has been also added so as to prevent the components of w from taking too large values

min w R(w) + C K k=1 ξ k (12) s.t. ξ k ≥ E G (u k (y k |w), h k (y k |w)) -E G (u k (y|w), h k (y|w)) -∆(y, y k ) , (∀y) (13)
The term R(w) can be chosen in several different ways (for instance, it is often set as a squared Euclidean norm 1 2 ||w|| 2 , or as a sparsity inducing norm like||w|| 1 ). It is easy to see that at an optimal solution of problem [START_REF] Finley | Training structural svms when exact inference is intractable[END_REF] each variable ξ k should equal to

ξ k = E G (u k (y k |w), h k (y k |w)) -min y E G (u k (y|w), h k (y|w)) -∆(y, y k ) . (14)
Furthermore, assuming that the dissimilarity measure ∆(y, y k ) decomposes in the same way as the MRF energy, i.e., it holds

∆(y, y k ) = p∈V δ p (y p , y k p ) + c∈C δ c (y c , y k c ) , (15)
we can define the following loss-augmented MRF potentials ūk (y|w), hk (y|w)

ūk p (• |w) = u k p (• |w) -δ p (• , y k p ) (16) hk c (• |w) = h k c (• |w) -δ c (• , y k c ) , (17)
which allow expressing the slack variable in [START_REF] Glocker | Dense image registration through MRFs and efficient linear programming[END_REF] as

ξ k = L k G (w), with L k G (w)
being defined as the following hinge loss term

L k G (w) := E G (ū k (y k |w), hk (y k |w)) -min y E G (ū k (y|w), hk (y|w)) . (18)
Therefore, problem [START_REF] Finley | Training structural svms when exact inference is intractable[END_REF] finally reduces to the following unconstrained optimization task

min w R(w) + C K k=1 L k G (w) , (19)
which shows that maximum-margin learning essentially corresponds to using the hinge loss term L k G (w) as the loss L(y k , y k (w)) in the empirical minimization task [START_REF] Alahari | Efficient piecewise learning for conditional random fields[END_REF]. Intuitively, this term L k G (w) expresses the fact that the loss will be zero only when the loss-augmented MRF with potentials ūk , hk attains its minimum energy at the desired solution y k .

Learning via Dual Decomposition

Unfortunately, even evaluating (let alone minimizing) the loss function L k G (w) is going to be intractable in general. This is because it is NP-hard to compute the term min y E G (ū k (y|w), hk (y|w)) involved in the definition of L k G (w) in [START_REF] Hinton | Training products of experts by minimizing contrastive divergence[END_REF]. To address this fundamental difficulty, here we propose to approximate the above term (that involves computing the optimum energy of a lossaugmented MRF with potentials ūk , hk ) with the corresponding optimum of a convex relaxation DUAL Gi (ū k , hk ) that is derived based on dual decomposition.

To accomplish that, as explained in section 3, we must first choose an arbitrary decomposition of the hypergraph G = (V, C) into sub-hypergraphs {G i = (V i , C i )} 1≤i≤N . Then, for the k-th training sample and for each sub-hypergraph G i , we define a slave MRF on G i that has its own unary potentials u k,i while inheriting the higher-order potentials hk . These slave MRFs are used for approximating min y E G (ū k (y|w), hk (y|w)) (i.e., the minimum energy of the loss-augmented MRF of the k-th training sample) with the following convex relaxation DUAL

Gi (ū k , hk ) DUAL Gi (ū k , hk ) = max {u k,i } 1≤i≤N N i=1 min y E Gi (u k,i (y), hk (y|w)) (20)
s.t.

i: p∈V i u k,i p = ūk p , (∀p ∈ V). (21)
If we now replace in [START_REF] Hinton | Training products of experts by minimizing contrastive divergence[END_REF] the optimum min y E G (ū k (y|w), hk (y|w)) with the optimum of the Inria above convex relaxation DUAL G i (ū k , hk ), we get the following derivation

L k G (w) = E G (ū k (y k |w), hk (y k |w)) -min y E G (ū k (y|w), hk (y|w)) (22)
≈ E G (ū k (y k |w), hk (y k |w)) -DUAL G i (ū k , hk ) (23)
= E G (ū k (y k |w), hk (y k |w)) - max {u k,i } 1≤i≤N N i=1 min y E G i (u k,i (y), hk (y|w)) (24)
= min

{u k,i } 1≤i≤N E G (ū k (y k |w), hk (y k |w)) - N i=1 min y E Gi (u k,i (y), hk (y|w)) , (25)
where in [START_REF] Komodakis | Learning to cluster using high order graphical models with latent variables[END_REF] we have made use of the following identity that holds for any function f

- max {u k,i } 1≤i≤N f ({u k,i }) = min {u k,i } 1≤i≤N (-f ({u k,i })) .
Due to the fact that the dual variables u k,i have to satisfy constraint [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF], i.e., ūk p = i: p∈V i u k,i p , the following equality stands in this case

E G (ū k (y k |w), hk (y k |w)) = N i=1 E G i (u k,i (y k ), hk (y k |w)) . ( 26
)
By substituting this equality into (25), we finally get

L k G (w) ≈ min {u k,i } 1≤i≤N N i=1 E Gi (u k,i (y k ), hk (y k |w)) -min y E Gi (u k,i (y), hk (y|w)) . (27)
Therefore, if we define

L k G i (w, u k,i ) := E Gi (u k,i (y k ), hk (y k |w)) -min y E Gi (u k,i (y), hk (y|w)) (28)
equation [START_REF] Komodakis | MRF optimization via dual decomposition: Message-passing revisited[END_REF] translates into

L k G (w) ≈ min {u k,i } 1≤i≤N i L k Gi (w, u k,i ) . (29)
Note that each L k G i (w, u k,i ) corresponds to a hinge loss term that is exactly similar to L k G (w) except from the fact that the former relates to a slave MRF on G i with potentials u k,i , hk , whereas the latter relates to an MRF on G with potentials ūk , hk .

The final function to be minimized results from substituting (29) into [START_REF] Jörg | A comparative study of modern inference techniques for discrete energy minimization problem[END_REF], thus leading to the following optimization problem

min w,{u k,i } 1≤k≤K,1≤i≤N R(w) + C K k=1 N i=1 L k Gi (w, u k,i ) (30)
s.t.

i: p∈Vi

u k,i p = ūk p , (∀k ∈ {1, 2, . . . , K}, p ∈ V). (31)
As can be seen, the initial objective function [START_REF] Jörg | A comparative study of modern inference techniques for discrete energy minimization problem[END_REF] (which was intractable due to containing the hinge losses L k G (•)) has now been decomposed into the hinge losses L k Gi (•) that are a lot easier to handle.

If a projected subgradient method [START_REF] Bertsekas | Nonlinear Programming[END_REF] is used for minimizing the resulting convex function, we get algorithm 1, for which the following theorem holds true: Theorem 1. If multipliers α t ≥ 0 satisfy lim t→∞ α t = 0, ∞ t=0 α t = ∞, then, the iterative updates in Algorithm 1 converge to an optimal solution of problem [START_REF] Kumar | Fast memory-efficient generalized belief propagation[END_REF].

Proof. We are going to make use of the following auxiliary variables λ k,i = {λ k,i p } p∈Vi , which are defined in terms of the variables u k,i = {u k,i p } p∈V i as follows

λ k,i p = u k,i p - u k p |I p | , (32)
where 1 ≤ k ≤ K, 1 ≤ i ≤ N , and

I p = {i|p ∈ V i }.
In this case, constraints (31) map into constraints {λ k,i } 1≤k≤K,1≤i≤N ∈ Λ, where the set Λ is given by

Λ = λ k,i 1≤k≤K,1≤i≤N | i∈I p λ k,i p = 0 . ( 33
)
To prove the theorem, we will proceed by showing that Algorithm 1 corresponds to applying the projected subgradient method to problem [START_REF] Kumar | Fast memory-efficient generalized belief propagation[END_REF] with respect to variables w, {λ k,i } 1≤k≤K,1≤i≤N . According to the projected subgradient method, variables w, λ k,i 1≤k≤K,1≤i≤N must be updated at each iteration using the following scheme [START_REF] Bertsekas | Nonlinear Programming[END_REF][START_REF] Shalev-Shwartz | Pegasos: Primal estimated subgradient solver for svm[END_REF]

w ← w -α t • dw (34) λ k,i ← Proj Λ (λ k,i -α t • dλ k,i ) . (35)
In the above, dw and dλ k,i 1≤k≤K,1≤i≤N denote the components of a subgradient of the objective function [START_REF] Kumar | Fast memory-efficient generalized belief propagation[END_REF] (with respect to w and λ k,i 1≤k≤K,1≤i≤N , respectively), and Proj Λ (•) denotes projection onto the feasible set Λ.

To compute these components, a subgradient of function L k G i (w, u k,i ) must be computed first, which in turns requires computing a subgradient of the term -min y E G i (u k,i (y), hk (y|w)), which is the only non-differentiable term used in the definition of L k Gi (w, u k,i ). This can be done by making use of the following well known lemma 7 Lemma. Let f (x) = max m=1,...,M f m (x), with f m being convex and differentiable functions of x. A subgradient of f at x 0 is given by ∇f m(x 0 ), where m = arg max m f m (x 0 ). Based on the above lemma, a subgradient of the term -min y E G i (u k,i (y), hk (y|w)) is given by the gradient vector -∇E G i (u k,i ( y k,i ), hk ( y k,i |w)), where y k,i denotes a minimizer for the energy E G i (u k,i (y), hk (y|w)) of the slave MRF defined on sub-hypergraph G i . This gradient vector has the following components:

- ∂E Gi (u k,i ( y k,i ), hk ( y k,i |w)) ∂w = - ∂ ∂w   p∈Vi u k,i p ( y k,i p ) + c∈Ci hk c ( y k,i c |w)   (32) = - ∂ ∂w   p∈V i u k p ( y k,i p |w) |I p | + λ k,i p ( y k,i p ) + c∈C i hk c ( y k,i c |w)   = - ∂ ∂w   p∈Vi u k p ( y k,i p |w) |I p | + c∈Ci hk c ( y k,i c |w)   7
The proof of this lemma follows from the fact that f

(x) ≥ f m (x) ≥ f m (x 0 ) + ∇f m (x 0 ) (x -x 0 ) = f (x 0 ) + ∇f m (x 0 ) (x -x 0 ). Inria (9) = - p∈Vi φ p ( y k,i p , x k ) |I p | - c∈Ci φ c ( y k,i c , x k ) , - ∂E G i (u k,i ( y k,i ), hk ( y k,i |w)) ∂λ k,i p (l) = - ∂E G i (u k,i ( y k,i ), hk ( y k,i |w)) ∂u k,i p (l) • ∂u k,i p (l) ∂λ k,i p (l) = - ∂u k,i p ( y k,i p ) ∂u k,i p (l) • ∂u k,i p (l) ∂λ k,i p (l) (32) = - ∂u k,i p ( y k,i p ) ∂u k,i p (l) = -y k,i p = l ,
where [ • ] denotes the Iverson bracket, i.e., it equals 1 if the expression in square brackets is satisfied, and 0 otherwise. Based on the above result, it is easy to verify that the components dw, dλ k,i 1≤k≤K,1≤i≤N of a total subgradient of the objective function [START_REF] Kumar | Fast memory-efficient generalized belief propagation[END_REF] are given by

dw = ∇R(w) + C   k,i,p φ p (y k p , x k ) -φ p ( y k,i p , x k ) |I p | + k,i,c φ c (y k c , x k ) -φ c ( y k,i c , x k )   (36) dλ k,i p (l) = C y k p = l -y k,i p = l . ( 37
)
Furthermore, after the update λ k,i ← λ k,i -α t •dλ k,i , eq. ( 35) also requires projecting the resulting λ k,i onto the feasible set Λ. This projection is equivalent to subtracting

i∈I p λ k,i p /|I p | from each λ k,i
p such that the sum i∈Ip λ k,i p remains equal to zero as required by the definition of Λ. Based on this observation and the definition of dλ k,i given in eq. ( 37), the combined update (35) reduces to

λ k,i p (l) + = α t C y k,i p = l - j∈I p y k,j p = l |I p | . (38)
All the above lead to the pseudocode of algorithm 1.

The proof now follows directly from the fact that the subgradient updates are known to converge to an optimal solution if the multipliers α t satisfy the conditions stated in the theorem (see Proposition 2.2 in [START_REF] Nedic | Incremental subgradient methods for nondifferentiable optimization[END_REF]). Interestingly, the key quantity to proving the convergence of the subgradient method is not the objective function value (which may have temporary fluctuations), but the Euclidean distance to an optimal solution, which is guaranteed to decrease per iteration. The proof of this is based on the fact that the angle between the current subgradient and the vector formed by the difference of the current iterate with an optimal solution is less than 90 degrees.

Let us pause for a moment to see what we have been able to accomplish so far. Comparing objective functions ( 19) and ( 30), we can immediately see that, thanks to the use of dual decomposition, we have managed to replace each term L k G , which is the hinge loss of a possibly difficult-to-solve high-order MRF on G, with the sum of the terms L k Gi 1≤i≤N that are the hinge losses of a series of simpler slave MRFs on sub-hypergraphs G k i 1≤i≤N . In this manner, we have essentially been able to reduce the difficult task of training a complex high-order MRF to the much easier task of training in parallel a series of simpler slave MRFs.

At a high level, to achieve this goal, the resulting learning algorithm operates by allowing each slave MRF to have its own unary potentials u k,i and by properly adjusting these potentials such that the estimated minimizer y k,i of each slave MRF coincides with the desired ground truth solution y k restricted on the nodes of G i . This is essentially done via updates [START_REF] Li | Learning for stereo vision using the structured support vector machine[END_REF] and [START_REF] Kumar | Exploiting inference for approximate parameter learning in discriminative fields: An empirical study[END_REF]. To get a better intuition for the role of these updates, note that the aim of the former updates is to modify u k,i such that the minimizers of different slave MRFs are consistent with Algorithm 1 Pseudocode of learning via dual-decomposition.

Input:

Training samples {x k , y k } 1≤k≤K , hypergraph G=(V, C), regularization constant C Unary and high-order feature functions {φp(•, •)} p∈V , {φc(•, •)} c∈C Learning procedure:

Choose decomposition {G i = (V i , C i )} 1≤i≤N of hypergraph G ∀k, i, p λ k,i p ← 0 , u k,i p ← λ k,i p + u k p |Ip| repeat K = {1,
k,i p ,x k ) |I p | + k,i,c φ c (y k c , x k ) -φ c ( y k,i c , x k ) w ← w -α t • dw // update u k,i ∀k ∈ K, i, p, l, λ k,i p (l) + = α t C y k,i p = l - j∈Ip y k,j p =l |Ip| ∀k ∈ K, i, p, u k,i p ← λ k,i p + u k p |Ip| until convergence
each other (i.e., they agree for the labels that are assigned to common nodes). Indeed, it is easy to verify that the right hand side of (38) equals to zero (which means that, as a result of this update, no change is applied to λ k,i p and thus to u k,i p as well) only if all minimizers of slave MRFs assign a common label to node p. On the contrary, if node p (contained, say, in only 2 sub-hypergraphs G i , G j ) is assigned 2 different labels by the corresponding minimizers y k,i , y k,j at the current iteration (i.e., it holds y k,i p = y k,j p ), then, update [START_REF] Li | Learning for stereo vision using the structured support vector machine[END_REF] results into the following updates for u k,i p (where = α t C/2)

u k,i p ( y k,i p ) += , u k,j p ( y k,i p ) -= , (39)
u k,i p ( y k,j p ) -= , u k,j p ( y k,j p ) += .

The above updates can be seen as trying to encourage the slave MRF minimizers computed at the next iteration to satisfy y k,i p = y k,j p , i.e., to assign a common label to node p. Furthermore, the role of the second updates ( 34) is exactly to encourage this common label to actually coincide with the ground truth label y k p .

Choice of decompositions G i 1≤i≤N and tighter approximations

The only requirement imposed by the above learning framework is that one should be able to compute the minimizers for the slave MRF subproblems. If this condition is satisfied, the previously described algorithm can automatically take care of the entire MRF training process. As a result of this fact, the proposed framework provides a great amount of flexibility. For Inria instance, a user is freely allowed to utilize different decompositions G i 1≤i≤N . As we will explain next, this fact can be utilized for improving the learning algorithm in various ways.

To that end, let F 0 denote the minimum of the original regularized loss function [START_REF] Jörg | A comparative study of modern inference techniques for discrete energy minimization problem[END_REF] and let F G i denote the minimum of loss function (30) that results from using decomposition G i .

The following theorem holds true Theorem 2. Loss F {G i } upper bounds F 0 , i.e., F 0 ≤ F {G i } Proof. By definition [START_REF] Jörg | A comparative study of modern inference techniques for discrete energy minimization problem[END_REF] it holds that

F 0 = min w R(w) + C K k=1 L k G (w) (18) = min w R(w) + C K k=1 E G (ū k (y k |w), hk (y k |w)) -min y E G (ū k (y|w), hk (y|w)) (41)
≤ min w R(w) + C K k=1 E G (ū k (y k |w), hk (y k |w)) -DUAL G i (ū k , hk ) (42) = min w R(w) + C K k=1 E G (ū k (y k |w), hk (y k |w)) - max {u k,i } 1≤i≤N N i=1 min y E Gi (u k,i (y), hk (y|w)) = min w R(w) + C K k=1 min {u k,i } 1≤i≤N E G (ū k (y k |w), hk (y k |w)) - N i=1 min y E G i (u k,i (y), hk (y|w)) = min w,{u k,i } 1≤k≤K,1≤i≤N R(w) + C K k=1 N i=1 E Gi (u k,i (y k ), hk (y k |w)) -min y E Gi (u k,i (y), hk (y|w)) (43)
= min

w,{u k,i } 1≤k≤K,1≤i≤N R(w) + C K k=1 N i=1 L k G i (w, u k,i ) = F {Gi} , (44)
where inequality ( 42) is true because

DUAL G i (ū k , hk ) is a convex relaxation of problem min y E G (ū k (y|w), hk (y|w)), while equality (43) is satisfied due to that E G (ū k (y k |w), hk (y k |w)) = N i=1 E Gi (u k,i (y k ), hk (y k |w)) since i∈Ip u k,i p = ūk p .
The above theorem implies that, by minimizing F Gi , one can also guarantee that the original loss F 0 will decrease as well. Not only that but, by appropriately choosing the hypergraph decomposition G i , we can also improve the approximation

F G i
to the true loss F 0 . This is true because the tightness of the convex relaxation DUAL G i depends crucially on the choice of decomposition G i . More specifically, we will say that decomposition Gj is stronger than decomposition G i (and we will denote this by G i < Gj ) if the convex relaxation from Gj is tighter than the relaxation from G i , i.e., it always holds DUAL Gi < DUAL Gj .

Under this notation, the following theorem is true

Theorem 3. If G i < Gj then F 0 ≤F Gj <F Gi , i.e., F Gj is a better approximation to F 0 than F Gi . F G i = min w,{u k,i } 1≤k≤K,1≤i≤N R(w) + C K k=1 N i=1 L k G i (w, u k,i ) (45) = min w R(w) + C K k=1 E G (ū k (y k |w), hk (y k |w)) -DUAL G i (ū k , hk ) , (46)
where the equality ( 46) is derived using a similar reasoning as in the proof of theorem 2 above.

Similarly, the following equality can be shown to hold true

F { Gj } = min w R(w) + C K k=1 E G (ū k (y k |w), hk (y k |w)) -DUAL Gj (ū k , hk ) . ( 47
)
By assumption it also holds G i < Gj , which means that the relaxation DUAL Gj (ū k , hk )

is tighter than the relaxation DUAL

G i (ū k , hk ), which in turn implies that DUAL G i (ū k , hk ) < DUAL Gj (ū k , hk ) . (48)
The theorem now follows directly by combining equations ( 46), ( 47) and [START_REF] Papandreou | Perturb-and-map random fields: Using discrete optimization to learn and sample from energy models[END_REF].

Given any MRF graph, it is always possible to choose a decomposition G single = G c c∈C , which contains a sub-hypergraph G c = (V c , C c ) for each clique c ∈ C where V c = {p|p ∈ c} and C c = {c}. In this case, each slave MRF consists of a single high-order clique. Due to this fact, such slaves are often very easy to optimize regardless of the complexity of the original MRF. As a result, the derived learning algorithm can have wide applicability. Furthermore, the convex relaxation DUAL G single (ū k , hk ) resulting from G single can be shown to coincide with the LP relaxation of the following integer programming formulation of MRF optimization [START_REF] Komodakis | Beyond pairwise energies: Efficient optimization for higher-order MRFs[END_REF]:

min z p yp ūk p (y p |w)z p (y p ) + c yc hk c (y c |w)z c (y c ) (49)
s.t. yp z p (y p ) = 1 , ∀p ∈ V ( 50
) yc:yp=l z c (y c ) = z p (l) , ∀c ∈ C, p ∈ c, l ∈ L (51) z p (•), z c (•) ∈ {0, 1} , (52)
In the above, z p (y p ) and z c (y c ) are binary indicator variables that exist respectively for each label y p of node p and each labeling y c of clique c. Note that such a relaxation extends the marginal polytope relaxation [START_REF] Chekuri | Approximation algorithms for the metric labeling problem via a new linear programming formulation[END_REF][START_REF] Schlesinger | Solution to structural recognition (MAX,+)-problems by their equivalent transformations[END_REF], which is commonly used for pairwise MRFs, to the case of higher-order MRF models. Of course, one can also choose decompositions Gj that are stronger than G single . Based on theorem 3 above, this can lead to using better approximations of the loss F 0 . This can be achieved, for instance, by taking advantage of the special structure that may exist in certain classes of MRFs. One characteristic example appears in [START_REF] Komodakis | Beyond pairwise energies: Efficient optimization for higher-order MRFs[END_REF] for the case of MRFs with the so-called pattern-based potentials. More generally, the following theorem holds true:

Inria Theorem 4. F Gj is a better approximation to F 0 than F G single only if decomposition Gj 1≤j≤N
has at least one sub-hypergraph Gj for which slave MRFs on Gj do not have the integrality property 8 .

Proof. As mentioned above, the MRF optimization problem min y E G (ū k (y|w), hk (y|w)) can be equivalently formulated as the following linear integer program:

min z p∈V y p ūk p (y p |w)z p (y p ) + c∈C y c hk c (y c |w)z c (y c ) (53) s.t z ∈ Z(G) , (54)
where the feasible set Z(G) is defined for any hypergraph G = (V, C) as follows

Z(G) = z ∈ Z(G) | z p (•), z c (•) ∈ {0, 1}, ∀ p ∈ V, c ∈ C , (55)
Z(G) =            z yp z p (y p ) = 1, ∀ p ∈ V yc:yp=l z c (y c ) = z p (l), ∀ c ∈ C, p ∈ c, l ∈ L z p (•) ≥ 0, z c (•) ≥ 0, ∀ p ∈ V, c ∈ C            . Let Gj = ( Ṽj , Cj ) 1≤j≤N be a hypergraph decomposition of G (i.e. ∪ N j=1 Ṽj = V, ∪ N j=1 Cj = C, Cj ∩ Cj = ∅, ∀j = j
) and let {u k,j } 1≤j≤N be the corresponding set of unary potentials for the slave MRFs of the k-th training sample, which satisfy equation [START_REF] Kumar | Efficiently solving convex relaxations for map estimation[END_REF], i.e.

j∈I p u k,j p = ūk p , (56)
where I p = {j|p ∈ Ṽj } (e.g. u k,j can be chosen as u k,j p = ūk p /|I p |). Using these potentials, the above linear integer program (53) can be equivalently expressed as

min z,{z j } 1≤j≤N N j=1   p∈ Ṽj yp u k,j p (y p )z j p (y p ) + c∈ Cj yc hk c (y c |w)z j c (y c )   (57) s.t. z j ∈ Z( Gj ) , ∀j ∈ {1, 2, . . . , N } (58)
z j p = z p , ∀j ∈ {1, 2, . . . , N }, p ∈ V . ( 59
)
The convex relaxation DUAL Gj (ū k , hk ) is derived by relaxing constraints ( 59) and then solving the resulting Lagrangian relaxation. Therefore, DUAL Gj (ū k , hk ) results from the above problem ( 57) by simply replacing constraints [START_REF] Szummer | Learning CRFs using graph cuts[END_REF] with the constraints z j ∈ CH Z( Gj ) , where CH(•) denotes the convex hull of a set.

If we now assume that all slave MRFs corresponding to decomposition Gj have the integrality property then, by definition, this implies that CH Z( Gj ) = Z( Gj ) (i.e. we can safely ignore the integrality constraints in ( 55)) and so DUAL Gj (ū k , hk ) further reduces to

min z,{z j } 1≤j≤N N j=1   p∈ Ṽj yp u k,j p (y p )z j p (y p ) + c∈ Cj yc hk c (y c |w)z j c (y c )   (60)
s.t. z j ∈ Z( Gj ) , ∀j ∈ {1, 2, . . . , N } (61)
z j p = z p , ∀j ∈ {1, 2, . . . , N }, p ∈ V . (62)
Due to constraints ( 56) and ( 62), the objective function [START_REF] Tappen | The logistic random field -a convenient graphical model for learning parameters for mrf-based labeling[END_REF] above is equal to the objective function [START_REF] Park | On learning higher-order consistency potentials for multi-class pixel labeling[END_REF]. Furthermore, constraints (61) are equivalent to constraints (54) after the integrality constraints in the latter have been replaced by non-negativity constraints on the z variables. Therefore, problem ( 60) is equivalent to the LP relaxation of the linear integer program [START_REF] Park | On learning higher-order consistency potentials for multi-class pixel labeling[END_REF], which, as mentioned earlier, corresponds to the dual relaxation derived from decomposition G single . This concludes the proof of the theorem.

Based on the above theorem, one can, for instance, provably derive better learning algorithms for pairwise MRF models just by using decompositions containing loopy subgraphs of small tree width (MRFs on such subgraphs can still be efficiently optimized via, e.g., the junction tree algorithm).

However, besides improving the accuracy of a learning algorithm, an appropriate choice of a decomposition G i can also improve the computational efficiency of that algorithm. For instance, consider the case of pairwise MRFs and a decomposition G tree = T i that consists entirely of spanning trees T i of an MRF graph G. Although in this case the accuracy of learning is not improved compared to G single (due to the fact that it holds DUAL G tree = DUAL G single and thus F Gtree = F G single [START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF]), the speed of convergence does improve in practice. The reason is because, when using convex relaxation DUAL Gtree , each slave MRF now covers a much larger number of nodes, which allows information to propagate faster across the whole graph G during the MRF dual decomposition updates.

More generally, computational efficiency can be significantly improved simply by choosing a decomposition that is specifically adapted to the class of MRFs we aim to train. For instance, if part of the energy of a MRF is known to be submodular we can take advantage of this fact simply by using that part as a slave. The very fast graph-cut based optimizers that exist for submodular energies can be used directly and will greatly reduce the computational cost of learning in this case.

Incremental and stochastic subgradient

To further improve computational efficiency we can also use an incremental subgradient method, which is well suited to objective functions that can be expressed as a sum of components, like in the case of objective function [START_REF] Kumar | Fast memory-efficient generalized belief propagation[END_REF] that is given by R

(•) + C K k=1 N i=1 L k G i (•)
, where K is the number of training samples and N the number of sub-hypergraphs in the decomposition. At each iteration of the incremental subgradient method, a step is taken along the subgradient of only one component, where this component can be picked either deterministically (by repeatedly visiting all components in a fixed order) or uniformly at random. A component for the above objective function can have the following form:

R(•) + C i∈S L k Gi (•) ,

Inria

where S denotes a subset of the set {1, 2, . . . , N }. In other words, at each iteration we need to consider the hinge losses L k G i (•) for only a subset of slave MRFs corresponding to the indices in S (in this case updates are similar to [START_REF] Li | Learning for stereo vision using the structured support vector machine[END_REF], [START_REF] Kumar | Exploiting inference for approximate parameter learning in discriminative fields: An empirical study[END_REF] but they need to take into account only a subset of slaves).

For instance, when using a randomized version of this scheme, we can decide to pick at each iteration the index of a training sample k randomly from {1, . . . , K}, and then also pick a subset S randomly from a predefined partition of the slave indices of the k-th sample. If S is always chosen to contain all slave indices of the k-th sample then this is essentially equivalent to the more well known stochastic subgradient algorithm, in which case the total subgradient with respect to w is computed analogously to [START_REF] Lafferty | Conditional random fields: Probabilistic models for segmenting and labeling sequence data[END_REF] as follows

dw = ∇R(w) + C   i,p φ p (y k p , x k ) -φ p ( y k,i p , x k ) |I p | + i,c φ c (y k c , x k ) -φ c ( y k,i c , x k )   . ( 63
)
To implement this learning scheme, we can modify Algorithm 1 by simply choosing K as a randomly picked index from {1, 2, . . . , K} at each iteration. Just like the subgradient method, the resulting algorithm is guaranteed to converge to an optimal solution since a theorem similar to Thm. 1 is known to also hold true for the incremental subgradient method [START_REF] Nedic | Incremental subgradient methods for nondifferentiable optimization[END_REF].

Experimental results

To demonstrate the generality and flexibility of our approach, in this section we present experiments and show results for a variety of test cases and scenarios. Such experiments include the training of pairwise and higher-order MRFs, the training by using different types of regularizers (including sparsity inducing ones) and/or different types of dissimilarity loss functions ∆(•, •), as well as the learning of appropriate models for a variety of vision tasks (including high-order models for pose-invariant knowledge-based segmentation, image denoising, stereo matching, as well as high-order Potts MRFs).

Image denoising

We begin by presenting experiments related to image denoising. For this purpose, we have created training and testing datasets consisting of synthetic piecewise constant images that have been corrupted by gaussian noise (see Fig. 3). To denoise these images we will make use of a pairwise MRF model whose unary potential is given by u p (l) = |l -I p |, where I p denotes image intensity at pixel p, and its pairwise potential h pq (•, •) is assumed to have the following form

h pq (l p , l q ) = V (|l p -l q |).
Our goal, in this case, is to learn the underlying function V (•), based on which the pairwise potentials are defined. This requires estimating a vector w = (w j ) 1≤j≤256 of size 256, each component of which corresponds to one value of V (•), i.e., V (j) = w j , ∀j ∈ {1, 2, . . . , 256}. Fig. 2(a) shows the resulting function V (•) as estimated when applying our method to a training set of 10 images, using the hamming loss as the dissimilarity function ∆(•, •). As can be observed, although V (•) has been learnt automatically from training data, it looks very much like a truncated linear function, which fully agrees with the common practice of using this type of discontinuity preserving potentials when dealing with piecewise constant images. Fig. 2(b) shows how the primal objective function [START_REF] Kumar | Fast memory-efficient generalized belief propagation[END_REF] varies during the course of our algorithm, thus demonstrating how quickly convergence takes place. We also compare to two other methods: the subgradient algorithm from [START_REF] Ratliff | online) subgradient methods for structured prediction[END_REF] 9 and the DLPW algorithm from [START_REF] Meshi | Learning efficiently with approximate inference via dual losses[END_REF]. Fig. 2(c) shows the average test error (for a test set of 10 noisy synthetic images) as a function of time for each algorithm. Our method manages to reduce the test error faster than DLPW. Similarly, it is a lot more efficient than the subgradient method [START_REF] Ratliff | online) subgradient methods for structured prediction[END_REF]. The inefficiency of the algorithm [START_REF] Ratliff | online) subgradient methods for structured prediction[END_REF], which relies on applying the subgradient method to the problem formulation [START_REF] Jörg | A comparative study of modern inference techniques for discrete energy minimization problem[END_REF], comes from the fact that the computation of a subgradient is much more expensive than in our method as it requires solving fully an LP-relaxation of problem min y E G (ū k (y|w), hk (y|w)), i.e., a relaxation that involves an MRF defined on the whole graph. We also show in Fig. 3 a sample result produced when denoising a test image using the function V (•) learnt by our method.

Stereo matching

We next test our method on stereo matching, which is a task that requires estimating a perpixel disparity map between two images of a stereoscopic pair. For this purpose, we will use a pairwise MRF with unary potentials given by u p (l) = |I left p -I right p-l |, where l represents discretized disparity, and I left , I right denote the left and right images, respectively. A very commonly used pairwise potential in this case is a gradient-modulated Potts model of the following form:

h pq (l p , l q ) = f (|∇I left p |)[l p = l q ], (64)
where p, q are neighboring pixels and ∇I left p = I left p -I left q represents the gradient of the left image at p. Our goal is to automatically learn the function f (•) that is used in the above formula [START_REF] Wang | Discriminative learning with latent variables for cluttered indoor scene understanding[END_REF] for assigning a discontinuity penalty based on the magnitude of the image gradient. Function f (•) can take 256 different values assuming integer intensities and so the positive vector w that we need to estimate will be of size 256 with w i = f (i). Furthermore, we also impose the restriction that vector w should belong to the set W = {w ≥ 0|w i ≥ w i+1 }, thus reflecting the a priori knowledge that f (•) should be a decreasing function. To accommodate this into our method, we must simply include an additional projection step10 w ← Proj W (w) at the end of each iteration of the projected subgradient algorithm, which is the only modification required. We show in Fig. 4(a) the resulting function f (•) that was estimated by our learning algorithm when using the hamming loss as the dissimlarity ∆(•, •) and a training set of two stereo pairs from the middlebury stereo dataset (the 'Tsukuba' and the 'Map' pairs were used). Using this function, we computed disparity maps for the 'Venus', 'Sawtooth', 'Bull' and 'Poster' stereo pairs from the middlebury dataset (see Fig. 5(a), Fig. 5(b)). The corresponding disparity error rates were 4.9%, 4.4%, 2.8%, 3.7% respectively. Fig. 5(b) also shows 3 different disparity maps that were computed for one of these test images using the function f (•) as estimated at 3 different iterations of our learning algorithm. Notice how the errors in the disparity are reduced as the algorithm converges. Fig. 4(b) shows how the primal objective (30) varies as a function of time during learning. Notice again that our method manages to successfully reduce this objective function very fast. On the contrary, the subgradient method [START_REF] Ratliff | online) subgradient methods for structured prediction[END_REF] is not very practical to use due to the large size of the MRF problems, which has as a result a considerable increase of the training time in this case. We should note at this point that the goal here is not to show that max-margin learning can achieve state-of-the-art performance on stereo-matching, but to demonstrate that our algorithmic framework provides a flexible and efficient way for MRF parameter estimation that is applicable to many different contexts.. For instance, state-of-the-art stereo matching methods (http://vision.middlebury.edu/stereo/eval/) typically make use of very elaborate unary potentials, utilize left-right consistency terms, take into account occlusions in their model, etc., whereas here we use a very basic model for stereo matching with very simple unary terms and features without even taking color information into account (grayscale images are used).

We also compare in Fig. 4(b) what happens when using two different decompositions during learning. Decomposition G row-col uses each row and column of the MRF grid as subgraphs for the slave MRFs, whereas G single uses each edge separately. As mentioned in section §6, G row-col is expected to lead to a faster convergence (due to the fact that each slave MRF now covers a larger part of the graph G, thus allowing information to propagate faster during the dual-decomposition updates), which is indeed what is observed in practice. purpose of compressing the size of the graph by eliminating as many redundant cliques as possible (through setting their corresponding weights to zero), thus producing a compact and efficient representation.

One important issue that the learning needs to address, in this case, relates to the poseinvariant properties of the learnt shape representation. In other words, it should be able to account for the fact that if y k is a ground truth shape, then, any transformed shape instance T (y k ), where T (•) represents a similarity transformation, is an equally good solution and should not be penalized during training. To accomplish that by our method, we make use of a dissimilarity function ∆(y, y ) that satisfies the following conditions, which ensure that pose invariance is indeed taken into account during the training process (∀y), ∆(T (y), y) = 0 .

The specific function that we use for this purpose decomposes into high-order terms as follows ∆(y, y ) = c∈C δ c (y c , y c ), where δ c (y c , y c ) = 0 if the triplets of points y c and y c connect by a similarity transform 1 otherwise . (68) The aforementioned L1 sparse higher-order shape model is used in conjunction with knowledgebased segmentation. In this context, following [START_REF] Xiang | 3d cardiac segmentation with pose-invariant higher-order mrfs[END_REF] we consider on top of the above third-order cliques, pair-wise cliques delineating the object boundaries in 2D, or third-order cliques corresponding to the object surface. The use of generalized Stokes theorem from differential geometry allows to convert regional integrals to surface ones and therefore combine edge-based terms with regional ones [START_REF] Xiang | Tagged cardiac mr image segmentation using boundary & regional-support and graph-based deformable priors[END_REF] (thus integrating both edge information and regional statistics towards seeking the separation in terms of intensity statistical means between the object and the background).

During training, a decomposition that assigns a single clique per slave has been used, in which case enumeration is applied for solving the resulting slave problems.

Our learning method was evaluated in this context using two different examples, a 2D hand data-set and a 3D medical imaging example (CT segmentation of the Left Ventricle). The 2D hand dataset contains 40 right hand examples (20 used for training and 20 used for testing), showing different poses (i.e., translations, rotations, and scales) and also movements between the fingers. Manual segmentations on the database are available and used as ground truth, while a number of 23 control points is used in the point distribution model. Fig. 6(a) shows how the learning objective function varies during training. As can be seen, the algorithm converges very fast despite having to deal with a large number of parameters. Moreover, it leads to a sparse model since the estimated w comprises only 5.6% non-zero components.

Some visual test results are shown in Fig 7 where red contours outline the results, and yellow contours represent initializations. As can be observed, thanks to the learnt model, satisfactory results are obtained even when noise or occlusions are present in the images. For example, in the first two images of the first row, the fingers are partially self-occluded which corresponds to shapes not seen at all during training, and yet our result is reasonable as it can still correctly localize the shape. In the 3 rd and 4 th images of the first row, noise and occlusions are present in the testing images: with a larger weight on prior term, our model shows its robustness. The first two rows also provide qualitative comparisons of our method with the Active Shape Models (ASM) segmentation algorithm [START_REF] Cootes | Active shape models: their training and application[END_REF] (blue contours). The third row shows results from additional tests that were conducted on a set of video images. For both quantitative and comparison purposes, we also plot in Fig 6(b) the Dice coefficients of our approach and ASM.

Regarding the 3D segmentation dataset, in our tests we have used one that contains 20 3D CT cardiac images. The volumes from different subjects have an approximate mean size of 512 × 512 × 250 voxels and the voxel size is about 0.35 × 0.35 × 0.5mm 3 . The point distribution model consists of 88 control points both on the myocardium surface as well as the atrium surface, while the coarse triangulated mesh is made up of 172 triangle faces. Some indicative results are shown in Fig 8, where the yellow contours correspond to our method, while the green contours represent the results from ASM models. As can be observed, the resulting model exhibits good accuracy on the boundary (the first two columns) and robustness to the papillary muscles in the blood pool (the last column). In addition, we provide in Fig. 6(c) a quantitative comparison of our algorithm with the ASM algorithm [START_REF] Cootes | Active shape models: their training and application[END_REF], the Random Walks algorithm [START_REF] Grady | Random walks for image segmentation[END_REF], and the method [START_REF] Xiang | 3d cardiac segmentation with pose-invariant higher-order mrfs[END_REF] as applied to the above 3D dataset (we present the corresponding Dice coefficients that were obtained). Note that method [START_REF] Xiang | 3d cardiac segmentation with pose-invariant higher-order mrfs[END_REF] does not learn the cliques and uses the complete graph (it is thus very computationally expensive taking more than 1 hour for one volume segmentation). On the contrary, we use a very sparse graph since the estimated w by our method contains only 0.9% non-zero components (the computation time in this case is about 3 minutes).

High-order Potts model

Last, we conclude the experimental part of the paper by showing some additional results on synthetic problems that are related to high-order MRF learning. More specifically, we applied our method to MRFs with P n Potts high-order potentials [START_REF] Kohli | P3 and beyond: Solving energies with higher order cliques[END_REF], which have the following form:

where l denotes any label from a discrete set of labels L. We assume that each value β c l is equal to the dot product of a vector of parameters w l with a feature vector x c l , i.e., β c l = w l • x c l , and the goal of learning includes estimating all vectors w l . For this we use synthetic data: we randomly sample unary potentials as well as feature vectors {x c l } and then we generate the values β c l of the high-order potentials based on a specified set of vectors {w l }. We then approximately minimize the resulting MRF using the method from [START_REF] Komodakis | Beyond pairwise energies: Efficient optimization for higher-order MRFs[END_REF], and the solution that we obtain is used as the ground truth for the current sample (we repeat this process to generate as many samples as we want). For the corresponding MRF hypergraph we assume that its nodes are arranged in a 2D grid and there exists a high-order clique for each subrectangle of size s × s in that grid. Our learning algorithm is applied by using a hamming loss for the dissimilarity function ∆(•, •), as well as a decomposition that assigns one clique per slave. Note that the minimization of each slave is very efficient as it takes time O(|L|) regardless of the size of the high-order clique. Fig. 9 shows an example of how fast the learning objective function decreases in this case (where we used a grid of size 50 × 50, the clique size was 3 × 3, |L| = 5, and we had 100 training samples). The main point we want to emphasize here is the efficiency of our method even when high-order MRF terms are present. It is also worth mentioning that the duality gap during optimization was typically small in this case as there was a large amount of agreement between the local solutions of the slave MRFs. This was true to a lesser extent for other experiments in the paper that involved more difficult high-order MRFs (e.g., pose-invariant knowledge based segmentation).

Conclusions

In this paper we have presented a general algorithmic framework for MRF/CRF training. Such a framework essentially manages to reduce the training of a complex high-order MRF model to the parallel training of a set of simple slave submodels. We have demonstrated that the derived learning scheme is sufficiently efficient and flexible (e.g., it can be applied to both pairwise and high-order models, it requires no submodularity assumptions, and it is easily adapted to the structure of a given class of MRFs). Moreover, it relies on solid mathematical principles and enjoys good theoretical properties. Due to all of the above, and given that learning problems are becoming increasingly important and challenging for a great variety of applications these days, we believe that our method can find use in a broad class of image analysis and computer vision tasks. It is also worth noting that this framework can be extended to handle the task of parameter estimation for latent CRF models [START_REF] Komodakis | Learning to cluster using high order graphical models with latent variables[END_REF], in which case a subset of variables remain unknown (i.e., hidden) during both training and test time. Although not thoroughly discussed in the present work, these, too, comprise a very important class of models in computer vision, with an increasingly large number of applications [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF][START_REF] Wang | Discriminative learning with latent variables for cluttered indoor scene understanding[END_REF].

Fig. 1 :

 1 Fig.1:(a) In MRF/CRF training, one aims to learn a mapping f : X → Y between a typically high-dimensional input space X and an output space of MRF/CRF variables Y . In stereo matching, for instance, the elements of the input space X correspond to stereoscopic images, and the elements of the output space Y correspond to disparity maps. (b) In general, the mapping f (x) is defined as minimizing the energy E G(u(y|w), h(y|w)) of an MRF/CRF model whose unary and higher-order potentials u(y|w), h(y|w) are parameterized by w (the potentials also depend on x, but this is omitted here to simplify notation). Therefore, to fully specify this mapping it suffices to estimate w, which is what parameter learning aims to achieve in this case. (c) Our framework reduces, in a principled manner, the training of a complex MRF model into the parallel training of a series of easy-to-handle slave MRFs. The latter can be freely chosen so as to fully exploit the problem structure, which, in addition to efficiency, contributes a sufficient amount of flexibility and generality to our method.

Fig. 2 :

 2 Fig. 2: (a) Learnt pairwise potential V (•), (b) primal objective (30), (c) and average test error as a function of time for the image denoising problem.

  (a) Energy: 6.29 × 10 4 (b) Energy: 8.42 × 10 4 (c) Energy: 5.71 × 10 4 (d) Energy: 6.08 × 10 4

Fig. 3 :

 3 Fig. 3: (a) Noisy test image (b) Denoised image when using a function V (•) estimated during the course of the learning algorithm (c) Denoised result when using the final V (•) (d) Ground truth image. We also show below each image the corresponding MRF energy computed using the final estimated V (•).

Fig. 4 :

 4 Fig. 4: (a) Learnt function f (•) and (b) primal objective (30) as a function of time for two different graph decompositions in the case of stereo-matching.

Fig. 6 :

 6 Fig. 6: (a) Learning objective function during MRF training with the hand dataset. Boxplots of Dice coefficients for (b) 2D hand segmentation, and (c) 3D left ventricle segmentation (the Dice coefficient is a similarity measure between sets X and Y , defined as 2|X∩Y | |X|+|Y | ).

  (a) Red contours: our results. Blue contours: ASM. Yellow contours: initialization. (b) Our results on video images with cluttered background.

Fig. 7 :

 7 Fig. 7: 2D hand segmentation results.

Fig. 8 :

 8 Fig. 8: 3D Segmentation results on cardiac CT volumes. (Top row) Our results. (Bottom row) ASM results.

  h c (y c ) = β c l if y p = l, ∀p ∈ c β c max otherwise ,

Fig. 9 :

 9 Fig. 9: Primal objective function during training of high-order Potts MRFs.

10 6 14 7

 1014 Choice of decompositions G i 1≤i≤N and tighter approximations Incremental and stochastic subgradient 18 8 Experimental results 19 8.1 Image denoising . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 8.2 Stereo matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 8.3 Higher order sparse MRF knowledge-based segmentation . . . . . . . . . . . . . . 22 8.4 High-order Potts model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr

  2, . . . , K} // for stochastic learning, use K = {pick randomly single index k ∈ {1, 2, . . . , K}} (see section 7) // compute minimizers of slave MRFs ∀k ∈ K, i, y k,i = arg min y E G i (u k,i (y), hk (y|w)) // optimize MRF with potentials u k,i , hk

	// update w
	dw ← ∇R(w) + C	k∈K,i,p	φ p (y k p ,x

k )-φ p ( y

The terms Markov Random Fields (MRFs) and Conditional Random Fields (CRFs) will be used interchangeably throughout.RR n°8645

RR n°8645

A hyperedge (or clique) c of a hypergraph G = (V, C) is simply a subset of the nodes V, i.e., c ⊆ V.RR n°8645

Slave MRFs could also have non-inherited high-order potentials. Here we consider only the case where just the unary potentials are non-inherited to simplify notation.

We should note, though, that none of these relaxations are guaranteed to be exact in the general case.Inria

In general, each MRF training instance can be defined on a different hypergraph G k = (V k , C k ), but here we assume G k = G, ∀k in order to reduce notation clutter.

For instance, if u k p (y p |w) = w T p,yp • φp (y p , x k ) and h k c (y c |w) = w T c,yc • φc (y c , x k ),we can define w as the concatenation of all vectors wp,y p and wc,y c , in which case each feature vector φp(yp, x k ) should be defined as a properly zero-padded extension of φp (y p , x k ) that has the same size as w (and similarly for φ c (y c , x k )).RR n°8645

We say that an MRF has the integrality property if and only if the corresponding LP relaxation of ( 49) is tight.RR n°8645

When applying method[START_REF] Ratliff | online) subgradient methods for structured prediction[END_REF], warm-starting has been used for the successive subgradient computations.Inria

The projection onto W = {w ≥ 0|w i ≥ w i+1 } is computed very fast via the so-called cyclic projection algorithm[START_REF] Yair | Parallel Optimization: Theory, Algorithms and Applications[END_REF], where we iteratively project (in a cyclic manner) onto the sets w ≥ 0, w i ≥ w i+1 , ∀i ∈ {1, 2, . . . , 255} until convergence.RR n°8645

Inria

* This work was partially supported by the ERC Starting Grant DIOCLES (ERC-STG-259112).

Higher order sparse MRF knowledge-based segmentation

We next apply our framework to the problem of knowledge-based image segmentation, focusing at the same time on the challenging task of learning sparse, pose invariant shape priors. For reasons of flexibility and generality, we use, in this case, a shape representation based on a point distribution model y = {y 1 , • • • , y n } that consists of a set V = {1, • • • , n} of n control points distributed on the boundary of the object of interest, where y p (p ∈ V) denotes the coordinates of the p th point. Additionally, we associate this model with a clique set C = {(p, q, r)|p, q, r ∈ V and p = q = r} consisting of all possible combinations of three points. Considering a triplet clique c = {p, q, r} ∈ C, the geometric shape of the clique y c = (y p , y q , y r ) is characterized in a pose invariant manner by the measurement of two inner angles (α c (y c ), β c (y c )) defined as follows

where notation --→ y p y q denotes the vector y p -y q . Given a training set of K shape instances {y k } 1≤k≤K , we assume that point correspondences exist between the point distribution models within the training set (without assuming that these shapes have been brought to the same referential). Each triplet c is thus associated with K instances {(α c (y 1 c ),

))} used for estimating a probability density p c (α c , β c ) of triplet c (where a standard probabilistic model based on a Gaussian distribution is employed for the angles (α c , β c )).

A shape prior can then be constructed with the accumulation of all triplet clique constraints. To accomplish this, we incorporate into the MRF energy the following higher-order potentials

As can be seen, these potentials are parameterized through a vector w = {w c } c∈C containing one component w c per clique c. Based on the above model, a clique c is essentially ignored if the corresponding element is close to zero, i.e., if it holds w c ≈ 0. Therefore, the use of w allows us to reduce the otherwise excessive number of higher order cliques, thus also reducing the computational cost of inference. Furthermore, given that the significance of the different triplets towards capturing the observed deformations of the training set is not the same, the role of the introduced vector w is to also weigh the contribution of those triplets that are retained in the model. Note that such a shape prior inherits pose invariance so that neither training samples nor testing shape needs to be aligned in a common coordinates frame. Moreover, it can capture shape variations even with a small number of training examples. When applying our max-margin learning method to this problem, we opt to make use of a sparsity inducing l 1 -norm regularizer, i.e., R(w) = ||w|| 1 . Such a choice serves the above Inria


Martine Boccara

Mathilde Carpentier

Jacques Chomilier

François Coste

Clovis Galiez

Joël Pothier

Alaguraj Veluchamy

Identifying distant homologous viral

come

Marine viruses have a huge impact on marine life: it is estimated that they daily kill about 20% of the ocean biomass. However, marine viruses are poorly known and characterized. One lever that could help to give better knowledge of marine viruses is marine metagenomics [START_REF] Suttle | Marine viruses -major players in the global ecosystem[END_REF]. Between 2009 and 2011, the TARA Ocean [START_REF] Karsenti | A holistic approach to marine eco-systems biology[END_REF] expedition sampled oceans at different depths, for different sizes of organisms. This project gave rise to a huge amount of scientific data, and specifically to metagenomic sequences. Standard annotation tools such as MEGAN [START_REF] Huson | Megan analysis of metagenomic data[END_REF], PhyloPythiaS [PRH + 11] and Phymm [START_REF] Brady | Phymm and phymmbl: metagenomic phylogenetic classification with interpolated markov models[END_REF], are either sequence-homology or composition based and they largely depends on the already available reference sequences. As viral sequences are highly divergent, the annotation of such data is very poor (in previous marine viral metagenomic studies, over 90% of sequences have no recognized homology [START_REF] Suttle | Marine viruses -major players in the global ecosystem[END_REF]). It is therefore necessary to change the paradigm of current methods to improve the detection of viral sequences in metagenomes using other sources of information such as protein structure. Our goals are both to develop new methods and databases and to contribute measuring the impact of virus over marine ecosystems. We want first to adapt recently developed methods combining sequence and structure information. A family of proteins, the capsid proteins, is present in every all viruses. Due to geometrical constrains on the viral capsid, these proteins are limited to a very small number of folds [START_REF] Krupovic | Double-stranded dna viruses: 20 families and only five different architectural principles for virion assembly[END_REF]. Moreover these folds are characteristic of the shape of the viral capsid [START_REF] Cheng | 3rd viral capsid proteins are segregated in structural fold space[END_REF]. Thus, identifying the fold of a protein present in a metagenomic dataset could help to identify the type of virus it is associated to.

In the PEPS VAG project, we aim at developing and adapting methods that allow designing robust sequential protein patterns taking advantage of structural information and applying them on a viral fraction of TARA Ocean metagenomic data. Aside from the novel developments, existing fold recognition methods like FROST will be adapted to our goals. FROST has been developed in the team of JF Gibrat with whom we collaborated [JRJ + 02]. Given a protein structure library, it assigns its most probable fold to a given sequence. We will build a library of capsid folds by comparing the protein structures of similar capsids. We will also add the information of MIRs (Most Interacting Residues) developed by one of the participating teams [PEB + 04] to improve its performance. MIRs are positions dispersed along the sequence, predicted from folding simulations on a lattice. They allow to give a signature of a fold, because they statistically correspond to residues compulsory on a structural point of view.

We are also developing a novel methodology in the PEPS VAG. The idea is to extract portions of proteins -called contact motifs -capturing strong structural conservation along with relevant sequential signals. We are heading to develop short signatures at the sequential level of characteristic structures, such as capsids, that can be used to find their occurrences on sequenced data. Our method identifies characteristic structural motifs of capsid proteins of a same fold from which we deduce a characteristic signal of the underlying sequence. We present here the first experiment we made on the viral fraction of station 23 of TARA Oceans at the Deep Chlorophyll Maximum depth.