7 Pages
English

Efficient Piecewise Learning for Conditional Random Fields

-

Gain access to the library to view online
Learn more

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


Subjects

Informations

Published by
Reads 35
Language English
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 (CRFs) offer a powerful tool for obtaining a probabilistic formulation for many applica-tions in Computer Vision and related areas [14, 15, 26]. ACRFis 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={Y1,∙ ∙ ∙, YN}. A labelling of aCRFcorresponds 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 pairwiseCRF. However, this assumption is not restrictive since anyCRFcan 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 suchCRFs [13].
y={y1:1,∙ ∙ ∙, y1:K, y2:1∙ ∙ ∙, yN:K}, whereNis the num-ber of vertices,i.e.|V |=N. Each binary indicator variable yi:k= 1, if the corresponding random variableYitakes the labelk∈ L, andyi:k= 0otherwise. Also,yi:k= 1,i. k Given some observed data (denoted byx), aCRFmodels the 2 conditional probability of a labellingy:as follows
1 Pr(y|x,θ) = exp(yi:kθhi(x)) k Z(θ) i∈V k∈L exp(yi:kyj:lθνij(x)),(1) kl (i,j)∈E k,l∈L d×1 whereθ= (θk,θkl)∈ Rare the parameters of theCRFvectors. The hi(x)andνij(x)represent features for the vertexi∈ Vand the edge(i, j)∈ Erespec-lexp(y h(x))denotes the tively. The unary potentiai:kθk i cost of the assignmentYi=k, while the pairwise potential (y y(x))denotes the cost of the assignment: expi:k j:lθkνij l Yi=kandYj=l. The normalizing factorZ(θ)given by:     Z(θexp() = yθhi(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 theCRFmodel, 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 aCRFstill remains a challenging problem, with considerable progress being made in the past few years. Recent methods for parameter estimation of aCRF can be broadly classified into three categories – maxi-mum likelihood-based methods [12, 21, 25], large margin 2 Using the notation of [1].