Efficient Piecewise Learning for Conditional Random Fields

Chris Russell

Description

Niveau: Supérieur, Doctorat, Bac+8
Efficient Piecewise Learning for Conditional Random Fields Karteek Alahari Chris Russell Philip H. S. Torr Oxford Brookes University Oxford, UK Abstract Conditional Random Field models have proved effec- tive for several low-level computer vision problems. Infer- ence in these models involves solving a combinatorial op- timization problem, with methods such as graph cuts, be- lief propagation. Although several methods have been pro- posed to learn the model parameters from training data, they suffer from various drawbacks. Learning these pa- rameters involves computing the partition function, which is intractable. To overcome this, state-of-the-art structured learning methods frame the problem as one of large mar- gin estimation. Iterative solutions have been proposed to solve the resulting convex optimization problem. Each iter- ation involves solving an inference problem over all the la- bels, which limits the efficiency of these structured methods. In this paper we present an efficient large margin piece- wise learning method which is widely applicable. We show how the resulting optimization problem can be reduced to an equivalent convex problem with a small number of con- straints, and solve it using an efficient scheme. Our method is both memory and computationally efficient. We show re- sults on publicly available standard datasets. 1. Introduction Conditional random fields (CRFs) offer a powerful tool for obtaining a probabilistic formulation for many applica- tions in Computer Vision and related areas [14, 15, 26].

• performing max


• efficient inference algorithms


• likelihood


• dimensional unary


• problem


• learning methods


• large margin


• argmin ?


• conditional random

Sujets

• Russell
• Learning
• Likelihood function
• Problem

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 35
• Langue: English

Extrait

Efficient Piecewise Learning for Conditional Random Fields

Karteek Alahari Chris Russell Philip H. S. Torr Oxford Brookes University Oxford, UK http://cms.brookes.ac.uk/research/visiongroup

Abstract

Conditional Random Field models have proved effec- tive for several low-level computer vision problems. Infer- ence in these models involves solving a combinatorial op- timization problem, with methods such as graph cuts, be- lief propagation. Although several methods have been pro- posed to learn the model parameters from training data, they suffer from various drawbacks. Learning these pa- rameters involves computing the partition function, which is intractable. To overcome this, state-of-the-art structured learning methods frame the problem as one of large mar- gin estimation. Iterative solutions have been proposed to solve the resulting convex optimization problem. Each iter- ation involves solving an inference problem over all the la- bels, which limits the efficiency of these structured methods. In this paper we present an efficient large margin piece- wise learning method which is widely applicable. We show how the resulting optimization problem can be reduced to an equivalent convex problem with a small number of con- straints, and solve it using an efficient scheme. Our method is both memory and computationally efficient. We show re- sults on publicly available standard datasets.

1. Introduction Conditional random fields ( CRF s) offer a powerful tool for obtaining a probabilistic formulation for many applica- tions in Computer Vision and related areas [14, 15, 26]. A CRF is defined over a graphG= (V,E), where Vdenotes a set of vertices andEis the set of edges, which specifies a pairwise relationship between the ver- 1 tices . The vertices represent discrete random variables Y={Y 1 ,∙ ∙ ∙, Y N }. A labelling of a CRF corresponds to a classification of the vertices by assigning a label to each vertex (variable) from a set of labelsL={1,∙ ∙ ∙, K}. In other words, a labelling is specified by a binary vector

1 Note that we have assumed a pairwise CRF . However, this assumption is not restrictive since any CRF can be converted to an equivalent pairwise CRF ,e.g. using a method similar to the one described in [31], and efficient inference algorithms are available for many such CRF s [13].

y={y 1:1 ,∙ ∙ ∙, y 1:K , y 2:1 ∙ ∙ ∙, y N:K }, whereNis the num- ber of vertices,i.e.|V |=N. Each binary indicator variable y i:k = 1, if the corresponding random variableY i takes the  labelk∈ L, andy i:k = 0otherwise. Also,y i:k = 1,∀i. k Given some observed data (denoted byx), a CRF models the 2 conditional probability of a labellingy:as follows

 1  Pr(y|x,θ) = exp(y i:k θh i (x)) k Z(θ) i∈V k∈L   exp(y i:k y j:l θν ij (x)),(1) kl (i,j)∈E k,l∈L d×1 whereθ= (θ k ,θ kl )∈ Rare the parameters of the CRF vectors. The h i (x)andν ij (x)represent features for the vertexi∈ Vand the edge(i, j)∈ Erespec-  lexp(y h(x))denotes the tively. The unary potentia i:k θ k i cost of the assignmentY i =k, while the pairwise potential  (y y(x))denotes the cost of the assignment: exp i:k j:l θ k ν ij l Y i =kandY j =l. The normalizing factorZ(θ)given by:     Z(θexp() = yθh i (x)) i:k k N i∈V y∈L k∈L     exp(y y i:k j:l θ k ν ij (x)),(2) l (i,j)∈E k,l∈L is the partition function. When using the CRF model, there are two main issues that need to be addressed: (i) How to set the value of the parametersθ; and (ii) How to per- form inference in order to obtain the optimal labelling,i.e. the labelling with the maximum conditional probability Pr(y|x,θ). The latter issue has received great attention and several inference algorithms have been proposed in the lit- erature (for an overview, see [26]). However, parameter es- timation of a CRF still remains a challenging problem, with considerable progress being made in the past few years. Recent methods for parameter estimation of a CRF can be broadly classified into three categories – maxi- mum likelihood-based methods [12, 21, 25], large margin 2 Using the notation of [1].