Learning Maximal Margin Markov Networks via Tractable Convex Optimization
Показано, что обучение марковской сети общего вида может быть представлено в виде задачи выпуклой оптимизации. Основная идея метода заключается в использовании LP-релаксации (max,+)-задачи непосредственно при формулировании задачи обучения....
Збережено в:
| Дата: | 2011 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2011
|
| Назва видання: | Управляющие системы и машины |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/82921 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Learning Maximal Margin Markov Networks via Tractable Convex Optimization / V. Franc, P. Laskov // Управляющие системы и машины. — 2011. — № 2. — С. 25-34. — Бібліогр.: 17 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-82921 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-829212015-06-12T03:02:14Z Learning Maximal Margin Markov Networks via Tractable Convex Optimization Franc, V. Laskov, P. Оптимизационные задачи структурного распознавания образов Показано, что обучение марковской сети общего вида может быть представлено в виде задачи выпуклой оптимизации. Основная идея метода заключается в использовании LP-релаксации (max,+)-задачи непосредственно при формулировании задачи обучения. It is shown that the learning of a general Markov network can be represented as a convex optimization problem. The key idea of the method is to use a linear programming relaxation of the (max,+)-problem directly in the formulation of the learning problem. Показано, що навчання марківської мережі загального вигляду може бути подано у вигляді задачі опуклої оптимізації. Основна ідея методу полягає у використанні LP-релаксації (max,+)-задачі безпосередньо при формулюванні задачі навчання. 2011 Article Learning Maximal Margin Markov Networks via Tractable Convex Optimization / V. Franc, P. Laskov // Управляющие системы и машины. — 2011. — № 2. — С. 25-34. — Бібліогр.: 17 назв. — англ. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/82921 004.93’1:519.157 en Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Оптимизационные задачи структурного распознавания образов Оптимизационные задачи структурного распознавания образов |
| spellingShingle |
Оптимизационные задачи структурного распознавания образов Оптимизационные задачи структурного распознавания образов Franc, V. Laskov, P. Learning Maximal Margin Markov Networks via Tractable Convex Optimization Управляющие системы и машины |
| description |
Показано, что обучение марковской сети общего вида может быть представлено в виде задачи выпуклой оптимизации. Основная идея метода заключается в использовании LP-релаксации (max,+)-задачи непосредственно при формулировании задачи обучения. |
| format |
Article |
| author |
Franc, V. Laskov, P. |
| author_facet |
Franc, V. Laskov, P. |
| author_sort |
Franc, V. |
| title |
Learning Maximal Margin Markov Networks via Tractable Convex Optimization |
| title_short |
Learning Maximal Margin Markov Networks via Tractable Convex Optimization |
| title_full |
Learning Maximal Margin Markov Networks via Tractable Convex Optimization |
| title_fullStr |
Learning Maximal Margin Markov Networks via Tractable Convex Optimization |
| title_full_unstemmed |
Learning Maximal Margin Markov Networks via Tractable Convex Optimization |
| title_sort |
learning maximal margin markov networks via tractable convex optimization |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2011 |
| topic_facet |
Оптимизационные задачи структурного распознавания образов |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/82921 |
| citation_txt |
Learning Maximal Margin Markov Networks via Tractable Convex Optimization / V. Franc, P. Laskov // Управляющие системы и машины. — 2011. — № 2. — С. 25-34. — Бібліогр.: 17 назв. — англ. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT francv learningmaximalmarginmarkovnetworksviatractableconvexoptimization AT laskovp learningmaximalmarginmarkovnetworksviatractableconvexoptimization |
| first_indexed |
2025-07-06T09:35:28Z |
| last_indexed |
2025-07-06T09:35:28Z |
| _version_ |
1836889700202184704 |
| fulltext |
УСиМ, 2011, № 2 25
UDC 004.93’1:519.157
V. Franc, P. Laskov
Learning Maximal Margin Markov Networks via Tractable Convex Optimization
Показано, что обучение марковской сети общего вида может быть представлено в виде задачи выпуклой оптимизации. Основная
идея метода заключается в использовании LP-релаксации (max,+)-задачи непосредственно при формулировании задачи обучения.
It is shown that the learning of a general Markov network can be represented as a convex optimization problem. The key idea of the
method is to use a linear programming relaxation of the (max,+)-problem directly in the formulation of the learning problem.
Показано, що навчання марківської мережі загального вигляду може бути подано у вигляді задачі опуклої оптимізації. Основ-
на ідея методу полягає у використанні LP-релаксації (max,+)-задачі безпосередньо при формулюванні задачі навчання.
Abstract
The learning of Markov networks constitutes a
challenging optimization problem. Even the pre-
dictive step of a general Markov network involves
solving an NP-complete max-sum problem. By
using the discriminative approach, learning of the
Markov networks from noisy examples can be
transformed to a convex quadratic program with
intractably large number of linear constraints. The
intractable quadratic problem can be attacked by
an approximate cutting plane (ACP) algorithm
proposed in [5]. The ACP requires repeatedly
solving a predictive step for finding the most vio-
lated constraint. The intractable search for the
most violated constraint is approximated by using
an (approximate) solver for the max-sum problem.
The use of the approximative max-sum solver in-
side the ACP algorithm brings two important
problems. First, the ACP algorithm is not guaran-
teed to converge to the optimal solution. Second,
the max-sum solvers are time consuming algo-
rithms which forbids using the ACP algorithm to
large scale problems. In this paper, we show that
learning of a general Markov network can be ex-
pressed as a convex optimization problem which
is solvable efficiently without calling any external
max-sum solver. The key idea, generalizing work
of [12], is to use a linear programing relaxation of
the max-sum problem directly in the formulation
of the learning problem. We show that the pro-
posed learning problem can be solved efficiently
by the Generalized Proximal Point Algorithm [7].
The empirical evaluation shows that our algorithm
speeds up learning of general Markov networks by
a factor of up to 20 compared to the ACP algo-
rithm.
1. Introduction
A Markov network is a powerful representation
of dependencies in structured objects. A Markov
network is defined by an undirected graph consist-
ing of nodes and edges
2
. The nodes cor-
respond to elementary objects while the edges rep-
resent possible structural interactions between them.
Each object t is characterized by an observ-
able variable tx which takes value from a set
and a hidden variable ty which takes values from
a finite set . Dependencies between observed an
a hidden variables are modeled for each object t
by functions );,( ttt yxq . Dependencies between
hidden variables of pairs of objects are modeled
for each pair tt , by functions );,( tttt yyg . In or-
der to apply a Markov network in practice the de-
pendency functions );,( ttt yxq and );,( tttt yyg
have to be specified. In principle, this can be done
by hand, but typically one assumes a certain pa-
rametrization n which controls the functi-
onal form of dependency functions tq and ttg .
The parameter is then learned from examples of
observations and corresponding hidden variables.
The Markov networks are typically used for pre-
diction of the hidden variables )|(= tyy t gi-
ven a tuple of observable variables )|(= txx t .
The predictive step amounts to solving
,);,();,(argmax
=);,(argmax=);(
tttt
tt
ttt
ty
y
yygyxq
yxHxh
(1)
26 УСиМ, 2011, № 2
where :h denotes the classifier (pre-
diction rule) given by the scoring function
:H which measures a match be-
tween the observations x and the hidden vari-
ables y . The integer programming problem on the
right-hand side of (1) is called a max-sum prob-
lem. We will denote the classification rule (1) as
the max-sum classifier. The max-sum problem is
NP-complete in general but it can be made tracta-
ble by imposing additional constraints on the
graph ),( or the quality functions ttg . The im-
portant examples of polynomially solvable max-
sum problems involve the problems with acyclic
graphs, graphs with a low tree-width (also called
simple nets), and the problems with supermodular
functions ttg . For a survey of relevant results we
refer to [9, 17].
A probabilistic interpretation of a Markov net-
work can be derived by assuming the observations
x and the hidden variables y to be realizations of
random variables )|(= tXX t and )|(= tYY t
distributed according to the Gibbs distribution
);,(exp
)(
1
=);,(
yxH
Z
yxP where )(Z is the
partition function. The Maximum A Posteriori
Prediction (MAP) of the hidden variables y given
observations x is carried out by evaluating
)|(argmax=* xyPy y which coincides with the
classifier (1).
The parametrization by offers two general
approaches for learning Markov networks from a
training set mmm yxyx )()},(,),,{( 11 .
A generative approach is based on the estimation
of parameters using a Maximum-Likelihood
(ML) principle. Such estimation is well known for
Hidden Markov Models with acyclic graphs (see
e.g. [11]). In a general case, however, the ML es-
timation is not tractable for Markov networks be-
cause no polynomial time algorithm is known for
computing the partition function Z(). A discrimi-
native approach is an alternative method which is
based on direct optimization of parameters in
order to minimize the prediction error of classifier
(1) computed on the training set. The discrimina-
tive learning inherently requires solving the in-
tractable predictive step of the max-sum classifier.
For this reasons most of the existing methods re-
strict the class of learned max-sum classifiers in
order to make the problem tractable. The restric-
tion is imposed either on the neighborhood graph
),( or on the quality functions ttg . In the next
paragraph we shortly review existing methods.
The methods for learning max-sum classifiers
with acyclic graph ),( are well understood [11,
3, 1, 2, 14]. Learning of the Associative Markov
Networks (AMN) with an arbitrary graph structu-
re was proposed by [13]. The AMN is the Markov
network with the quality functions ttg restricted
in a way similar to the Potts model. Even though
the predictive step of the AMN is not tractable,
the learning algorithm in [13] alleviates the prob-
lem by using a kind of Linear Programming (LP)
relaxation. By this manner, the learning problem
is transformed into a Quadratic Programming (QP)
task with a polynomial number of constraints. Le-
arning of the max-sum classifiers with super-modu-
lar quality functions ttg was proposed in [5]. In this
case, the learning leads to a QP task solvable in
polynomial time by the Cutting Plane Algorithm
(CPA). Another polynomially learnable class is
formed by the max-sum classifier with a strictly
trivial equivalent (STE) [5]. The max-sum prob-
lems with STE are those whose response can be
computed exactly via LP relaxation. Provided the
training examples are separable, learning of the
max-sum classifier with STE can be transformed
to solving a system of strict linear inequalities
manageable by the Perceptron algorithm. In the
case of non-separable examples, the max-sum
classifier with STE can be learned by minimizing
a regularized upper bound on the empirical risk
with zero-one loss function. The only existing ap-
proach for learning truly general max-sum classi-
fiers was proposed in [5]. The intractable learning
problem is attacked by an Approximate Cutting
Plane (ACP) algorithm. The ACP requires repeat-
edly solving a predictive step for finding the most
violated constraint. The intractable search for the
most violated constraint is approximated by using
an (approximate) solver for the max-sum problem.
УСиМ, 2011, № 2 27
The use of the approximative max-sum solver in-
side the ACP algorithm brings two important
problems. First, the ACP algorithm is not guaran-
teed to converge to the optimal solution. Second,
the max-sum solvers are time consuming algo-
rithms which forbids the use of the ACP algorithm
to large scale problems.
In this paper, we concentrate on learning of the
max-sum classifier with a general neighborhood
graph ),( and general quality functions ttg .
We show that the learning of a general max-sum
classifier from non-separable examples can be ex-
pressed as a convex optimization problem solv-
able efficiently without calling any external max-
sum solver. Our approach, named LP-M3N formu-
lation, generalizes the Maximum Margin Markov
Network (M3N) algorithm for learning of the As-
sociative Markov Networks (AMN) [13]. We show
that the LP-M3N problem can be solved efficiently
by the Generalized Proximal Point Algorithm. We
show experimentally that our algorithm speeds up
the learning by a factor of up to 20 compared to
the ACP algorithm.
The paper is organized as follows. Section 2
describes the LP relaxation of the max-sum prob-
lems which is essential for our approach. The ex-
isting M 3 N methods for learning max-sum classi-
fiers are outlined in Section 3. Our LP-M3N for-
mulation is described in Section 4. The General-
ized Proximal Point Algorithm for optimization of
the LP-M3N problem is given in Section 5. Sec-
tion 6 presents an empirical evaluation and Sec-
tion 7 concludes the paper.
2. Linear Programming Relaxation
Computing the output of a classifier (1) re-
quires solving the max-sum problem which is NP-
complete in general. An approximate solution can
be found by the linear programming (LP) relaxa-
tion proposed by [8] and later reinvented by
[6, 16]. We introduce only the basic concepts of
the LP relaxation necessary for this article. For
more information we refer to a survey in [17].
Let ),( denote an undirected graph
with edges },,|)},(),,{{(= yyttytyt .
Each node ),( yt and each edge
)},(),,{( ytyt is assigned a number )(yt
and ),( yytt , respectively. Let
2|||||||| be
an ordered tuple which contains elements )(yt ,
),( yt and ),( yytt , )},(),,{( ytyt .
The LP relaxation of (1) reads
.,,0)(,,1)(
,,,)(),(
)];,(),(
);,()([argmax
2),(
*
ytyty
yttyyy
tosubject
yygyy
xyqy
tt
y
ttt
y
tttt
yytt
ttt
yt
(2)
We denote the objective of (2) by );,( xP . It
can be seen that solving (2) with an additional
constraint
2||||||||{0,1} is an integer linear
programming (ILP) problem equivalent to (1). It
implies that );,(max);,( * yxHxP y holds
in general. Further, we introduce the Lagrange dual
of the LP task (2) which will be later used to con-
struct the learning algorithms. Let :tt and
:tt be a pair of functions introduced for
each pair of neighbouring objects tt , that is,
we have ||2 functions in total. We will use
||||2 to denote an ordered tuple which con-
tains elements )(ytt , },{ tt , y and )(ytt ,
},{ tt , y . Let further }},{|{=)( ttttN
denote the set of objects neighbouring with the
object t . Let us define a convex function
.)]()(),([max
)]();,([max);,(
2},{
)(
tttttttttt
yytt
t
tNt
tt
yt
yyyyg
yyxqxD
(3)
It can be shown that the dual of the LP relaxa-
tion (2) is equivalent to
* ( , ; ).argmin D x
(4)
By the weak duality theorem, ( , ; )D x
*( , ; )P x , , and thus also ( , ; )D x
,);,(max yxHy . It means that );,( xD
28 УСиМ, 2011, № 2
provides an upper bound on the optimal value of
the max-sum problem which will be later used to
construct the learning algorithms. The problem (4)
can be interpreted as searching for the best (that
is, minimal) upper bound.
Provided the LP relaxation is tight, one can
compute the maximizer y = arg );,(max yxHy
from * by solving an instance of the Constraint
Satisfaction Problem (CSP). The CSP is a special
case of the max-sum problem when the quality
functions tq , ttg attain values ,0}{ . The CSP
itself is NP-complete in general. There is no guar-
antee that we can compute *y even if =);,( * xD
);,(= * yxH holds and thus computing the opti-
mal solution *y is a more complex than comput-
ing the value );,( * yxH which can be always ap-
proximated by );,( * xD solvable in a polyno-
mial time.
The LP tasks (2) and (4) are not the only possi-
ble way to approximate the max-sum problem (1).
If the graph ),( can be easily decomposed to
acyclic sub-graphs with non-overlapping edges,
the task (4) can be replaced by an equivalent prob-
lem potentially more suitable for optimization
[10]. Let us consider a grid graph ),( useful in
image analysis, that is, ,1,=|),{(= iji Height,
}Width,1,= j and ),(|)},(),,{{(= jijiji
1}|=|||,),(, jjiiji . We define
the sets of horizontal H and vertical V edges as
follows
,}Width<,1Height1|)},(1),,{{(= jijijiH
.}Width,1Height<1|)},(),1,{{(= jijijiV
It can be seen that VH = and
}{= VH . Let :t be functions de-
fined for each object and let |||| denote
an ordered tuple which contains elements )(yt ,
t , y . It is easy to see that
)();,(
2
1
=);,( ttttt
t
yyxqyxH
),()(
);,(
2
1
),(
tttt
tt
tt
ttt
t
tttt
tt
yygy
yxqyyg
V
H
(5)
holds . Taking the maximum over the terms in
(5) independently we get
,),(
)();,(
2
1
max
),()(
);,(
2
1
max=);,(
tttt
Vtt
ttttt
ty
tttt
Htt
tt
ttt
ty
yyg
yyxq
yygy
yxqxU
(6)
which is obviously an upper bound on the optimal
value );,(max yxHy . The upper bound U(x,
, ) can be evaluated efficiently since it involves
two max-sum problems with an acyclic neighbor-
ing structure solvable by the dynamic program-
ming. It can be proved [10] that the upper bounds
);,( xD and );,( xU are equivalent in the
sence that
.);,(min=);,(min
xUxD
Minimizing the bound );,( xU involves smal-
ler number of variables compared to the bound
);,( xD and thus is preferable for large scale
problems.
3. Maximal Margin Markov Networks
In this section, we describe a discriminative
approach for learning the quality functions tq ,
ttg . We consider learning from a single example
)ˆ,ˆ( yx . This assumption considerably
simplifies notation but all the introduced algo-
rithms can be easily extended for a finite number
of examples.
Let :L be a loss function pe-
nalizing a prediction );( xh by a penalty L(y,
h(x; )) provided the true hidden variables are y.
УСиМ, 2011, № 2 29
We assume that L is additive over the objects
t , that is, ),(=),( tttt
yyLyyL
, where
:tL , t . In addition, we assume
that 0=),( yyLt for yy = and 0>),( yyLt oth-
erwise. An example of a proper loss function is
the Hamming distance ]][[=),( ttt
yyyyL
where 1=]][[ A if A is valid and 0=]][[ A other-
wise. Further, we assume that the functions
);,( yxqt and );,( yyg tt are linear in the pa-
rameter n , that is,
,),,(=),(
),,(=);,(
yyyyg
andyxyxq
tttt
tt (7)
where n
t : and n
tt : are
arbitrary fixed mappings. Under the assumption
(7), the max-sum classifier (1) becomes an in-
stance of the linear multiclass classifier
),(),(,argmax=);( tttt
tt
ttt
ty
yyyxxh
,),(,argmax
=)(),(,argmax=
yx
yyx
y
gq
y
where nq : , ng : and
n : are mappings constructed
from t and tt .
Given an example )ˆ,ˆ( yx , the parameter vector
can be learned by minimizing the following con-
vex problem
2* 1
= ( ) := ( ) ,argmin
2n
F C R
(8)
where
ˆ ˆ( ) = [ ( , ) , ( , ) ]max
ˆ ˆ, ( , ) ,
y Y
R L y y x y
x y
(9)
and 0>C is some prescribed constant. The max-
sum classifier with parameters obtained by solv-
ing (8) is called the Maximum Margin Markov
Network (M3N) [14]. In the sequel, we will denote
(8) as the M3N problem.
The objective function )(F of the M3N prob-
lem is composed of the quadratic regularization
term
21
2
and the function )(R which is a
convex approximation of the empirical risk, that
is, ));(,()( xhyLR , . The quadratic term
21
2
and the regularization constant 0>C re-
gularizes the solution in order to prevent the clas-
sifier from over-fitting. The constant C is typi-
cally tuned on a validation set. It can be shown
that the quadratic term in the objective is equiva-
lent to restricting the admissible parameters
into a ball with a radius proportional to the con-
stant C . In addition, for sufficiently large C the
problem (8) becomes equivalent to solving
* = ( )argmin R .
Though the M3N problem is convex it is not
tractable due to the function )(R whose evalua-
tion involves solving an instance of the max-sum
problem which is NP-complete. The complexity
of the M3N problem becomes more apparent if it
is transformed into an equivalent quadratic pro-
gramming (QP) problem with ||| linear con-
strains and 1n variables.
We now summarize the existing methods for
solving (8). We consider only the methods that can
deal with an arbitrary neighborhood graph ),( .
Associative Markov Networks (AMNs) [13].
AMNs is the Markov Network with the quality
functions satisfying 0=),( yyg tt , for yy . [13]
proposed to replace the intractable function )(R
in the definition of (8) by its LP relaxation which
is particularly simple for the AMNs. In that man-
ner the intractable M3N problem (8) is approxi-
mated by a tractable QP task with )|||(| 2O
linear constrains.
Super-modular max-sum classifiers [5]. Un-
der the assumption that the quality functions ttg
are super-modular, the max-sum problem can be
solved in polynomial time. In turn, the value of
the function )(R and its sub-gradient can be
computed which makes it possible to solve the
30 УСиМ, 2011, № 2
M3N problem efficiently by a variant of the cut-
ting plane algorithm (CPA). The CPA of [5] finds
-optimal solution of (8) in
1
O iterations.
A max-sum classifier with strictly trivial
equivalent (STE) [5]. The max-sum problems with
STE are those whose response can be computed
exactly by the LP relaxation. In the case of sepa-
rable training examples, the parameters of the
max-sum classifier can be found by solving a set
of strict linear inequalities whose number is pro-
portional to )|||(| 2O . In turn, the parameters
can be found by the Perceptron algorithm which is
guaranteed to stop in a finite number of iterations.
In the case of non-separable training examples,
the parameters can be learned by minimizing a
quadratically regularized upper bound on the
training error defined for a zero-one loss function
(the loss is 0 if all labels are correctly classified
otherwise the loss is 1). The learning problem
amounts to solving a QP task with )|||(| 2O
linear constraints.
General Markov Networks [5]. The M3N pro-
blem can attacked by an Approximate Cutting
Plane (ACP) algorithm. The APC algorithm re-
quires computation of the value of )(R and its
sub-gradient which involves solving an instance
of an intractable max-sum problem. can be solved
approximately by the LP relaxation. The resulting
algorithm is guaranteed to stop in a finite number
of iterations, however, there are no guarantees on
the precision of the found solution. Moreover, the
ACP algorithm is computationally demanding as
it calls in each iteration the max-sum solver for
each training example. Note, that the max-sum
solvers are time consuming as they solve a large-
scale linear program as well as the CSP problem
to obtain the labels.
To sum up, there is currently no efficient
method for learning parameters of a general max-
sum classifier from non-separable examples. To
close this gap, we show in Section 4 that the ob-
jective function of the M3N problem can be re-
placed by another convex function whose value and
sub-gradient can be computed efficiently without
a need to call an external max-sum solver. In turn,
the learning problem can be solved by a plethora
of algorithms for non-smooth optimization. We
describe one of such algorithm in Section 5.
4. Proposed LP-M3N formulation
The key idea is to replace the intractable max-
sum problem in the definition of the M3N problem
(8) by its upper bound derived from the LP relaxa-
tion (c.f. Section 2). Henceforth, we concentrate
on the max-sum problem with a grid graph ),(
whose optimal value can be upper bounded by (6).
Note, however, that the derivation for a general
neighborhood graph using the bound (3) is ana-
logical.
Using (6) we can upper bound the maximiza-
tion term in (9) as follows
,)(,),ˆ(
)(),ˆ(
2
1
,max)(,
),ˆ()(),ˆ(
2
1
,max
),()(),ˆ(
);,ˆ(
2
1
max),(
)(),ˆ();,ˆ(
2
1
max
]),ˆ(,),ˆ([max
#
yyyL
yyxy
yyLyyx
yygyyyL
yxqyyg
yyyLyxq
yxyyL
gq
y
gq
y
tttt
Vtt
ttttt
ttt
ty
tttt
Htt
tttttttt
ty
y
(10)
where ||||: is a mapping constructed
appropriately. We define a function
.)ˆ,ˆ(,)(,
),ˆ()(),ˆ(
2
1
,max
)(,),ˆ(
)(),ˆ(
2
1
,max=),(
yxy
yyLyyx
yyyL
yyxR
gq
y
gq
y
(11)
УСиМ, 2011, № 2 31
Note, that ),( R and )(R are two different
functions distinguished by their arguments. By
(10) we have that ),()( RR , |||| , that
is, ),( R is an LP-relaxation based upper bound
on )(R . By replacing )(R with ),( R in the
definition of M3N problem (8) we obtain
| || |θ ,
2
ˆ ˆ( , ) = ( , ) :=argmin
1
:= ( , ) .
2
yn
F
C R
(12)
We will denote (12) as the LP-M3N problem. It
is seen, that the objective ),( F is convex and it
upper bounds the objective of the original M3N
problem (8) . An advantage of the LP-M3N prob-
lem is that its objective value ),( F and sub-
gradient ||||)],();,([=),(
nFFF
can be computed efficiently as follows:
,)(,),ˆ(
)(),ˆ(
2
1
,max=~
yyyL
yyxy gq
y
,)(,),ˆ(
)(),ˆ(
2
1
,max='~
yyyL
yyxy gq
y
1
ˆ( , ) = ( , ) ( )
2
1
ˆ ˆ ˆ( , ') ( ') ( , ) ,
2
q g
q g
F C x y y
x y y x y
,)]'~()~([=),( yyCF
21
( , ) = , ( , ) , ( , ) .
2
F F F
Recall, that the maximization tasks are solvable
by the dynamic programming.
5. Generalized Proximal Point Algorithm
The objective function ),( F of the LP-M3N
problem is convex and non-differentiable. This
suggest usage of the methods from non-smooth
optimization. The simples options is the plain sub-
gradient algorithm which starts from an arbitrary
0( , )0 and then iteratively computes
and
F
F
tt
tt
ttt ),(
),(
1
,
),(
),(
1
tt
tt
ttt
F
F
where ,,0 is a prescribed sequence of posi-
tive numbers satisfying
=
0= tt
and tt 0lim
= 0. The sub-gradient algorithm is guaranteed to
converge to the optimal solution of the LP-M3N
problem.
In this section, we describe another algorithm
for non-smooth optimization which often conver-
gences faster compared to the plain sub-gradient
algorithm. In particular, we use the Generalized
Proximal Point Algorithm (GPPA) [7]. Let us de-
fine an auxiliary objective function
,
1
),(:),(
2
t
t
t FF
(13)
where |||| t is a vector and 0>t is a sca-
lar. The added quadratic term makes the auxiliary
objective ),( tF strictly convex and more ame-
nable to minimization compared to the original
objective ),( F .
There are several methods which can solve the
auxiliary problem (13) efficiently. We use the
Bundle Method (BM) algorithm described in [15].
The BM algorithm only requires to access the op-
timized objective via its value and sub-gradient.
The BM algorithm is guaranteed to find -optimal
solution in
1
O time. In its inner loop, the BM
algorithm solves instances of convex QP of a
small size with particularly simple linear con-
straints. We used the QP solver described in [4].
It is seen that ),( tF upper bounds ),( F .
The approximation gets tighter for larger t and
for t closer to the optimal vector ̂ . The Gener-
alized Proximal Point Algorithm 1 iteratively tight-
ens the approximation by applying block-coordinate
minimization on the auxiliary objective ),( tF .
32 УСиМ, 2011, № 2
Algorithm 1: Generalized Proximal Point
Algorithm for LP-M 3 N Problem
1. input & initialization: Set 00 , and se-
lect a sequence of positive numbers ,,0 ;
2. repeat;
3. Solve the auxiliary problem
),(argmin=),(
||||,
11
t
n
tt F
; (14)
4. until convergence.
It is easy to see that the sequence ,),,( 11
),( tt generated by Algorithm 1 monotonically
decreases the objective function ),( F . Indeed,
by a simple algebra we get that
.
1
),(),(
2
111 tt
t
tttt FF
There exists many convergence results regard-
ing the standard PPA. Unfortunately, this is not
the case for the GPPA which has not been studied
so intensively. The result closest to our problem is
the following convergence theorem proved in [7]:
Theorem 1 Suppose ],(: mnF
is a function which is convex and inf-compact,
that is, for each the set }),(|),{( F is
compact. Let ),(,),,( 00 be any sequence
generated by Algorithm 1. Then
* *
,
( , ) = = ( , ).lim mint t
t
F F where F F
Unfortunately, the theorem cannot be applied
to our problem as the objective function ),( F
is not inf-compact. Nevertheless, we provide a
convincing empirical study of the convergence
speed of Algorithm 1 in Section 6.
Algorithm 1 is specified up to the choice of the
sequence of t and a practical stopping condition.
A proper selection of the sequence is delicate as it
involves trade-off between the number of itera-
tions and the complexity of the auxiliary problem
(14). That is, higher values of t leads to a large
decrease in the objective value, however, the op-
timization of the auxiliary problem (14) gets
harder and vice versa. Based on experiments, we
found useful to use a geometrical sequence
att =1 , where 1>a and 0>0 are selected
constants.
In the comparison presented in Section 6 we
stop the algorithm when the value of ),( F
drops below a given threshold which is known a
priory. In practice, when no such threshold is pro-
vided, one can stop the algorithm based on ob-
serving the objective function. Alternatively, the
algorithm can be stopped when the added quad-
ratic term in the auxiliary function ),( tF gets
sufficiently small meaning that ),( tF is a tight
approximation of ),( F . That is the stopping
condition may read
.
1 2
1
ttt
(15)
It is clear, that the stopping condition (15) is
satisfied in a finite number of iterations for any
0> . However, we do not have any result which
would relate a solution ),( satisfying the stop-
ping condition (15) to the optimal solution of the
LP-M3N problem (12). Derivation of theoretically
grounded stopping condition will be a subject of
our future research.
6. Experiments
We consider a problem of learning the max-
sum classifier (1) for their color image segmenta-
tion. The training examples are color images
along with ground-truth segmentation produced
by a human annotator. The task is to learn the
classifier (1) which produces the segmentation
similar to the human. We use the Hamming loss
ˆ ˆ( , ) = [ ]t tt
L y y y y .
The images are snapshots of a shape-sorter
puzzle placed on a carpet. Figure shows example
images. The task is to segment the input images
into color blobs corresponding to the carpet and 5
colored puzzle pieces. The images are split into
training set (14 images 100][100 pixels), the
validation set ( 4 images 100][100 pixels) and
testing set ( 4 images 200][200 pixels).
The objects correspond to pixels of the in-
put image. The edges captures the 4-neighborho-
od structure of the pixels, that is, the graph ),(
УСиМ, 2011, № 2 33
is a discrete grid (c.f. Section 2 for definition).
The observable state },{1,= Xt Nx is a
natural number which encodes the RGB color of
the t-th pixel. We used 3 bits per each color chan-
nel which means 512=2= 33
XN . The assignment
of the t-th pixel to a segments is determined by the
label },{1,= Yt Ny . The number of seg-
ments is 6=YN . We further assume that func-
tions :tq and :ttg are dis-
crete functions which do not depend on the pixel
t (called homogeneous model). Thus the di-
mension of the parameter vector is YX NNn =
YY NN .
Example images and their segmentation predicted by a max-sum
classifier learned from examples
We compared the Approximate Cutting Plane
(ACP) algorithm [5] against the proposed Gener-
alized Proximal Point Algorithm (GPPA) defined
by Algorithm 1. We are not aware of any other
discriminative approach able to solve this task. To
solve the predictive step required by the ACP al-
gorithm, we used a highly optimized implementa-
tion of the Augmenting DAG algorithm described
in [17]. Both ACP and GPPA require to compute
the objective value, its sub-gradient and also to
solve an instance of the QP task. We used exactly
the same implementation of these sub-tasks in
both methods. Both ACP and GPPA return an up-
per bound of the objective value of the M3N prob-
lem (8). This enables a fair comparison in terms of
the objective function and the computational time
(the wall clock time). The ACP algorithm also
produces a lower bound )(LBF on the optimal va-
lue )( *F . First, we run the ACP algorithm with
stopping condition )(( UBF ( )) / ( ) 0,01LBF F
(precision 0.001 was not already attained by the
ACP). Second, we run the proposed GPPA until it
reached the precision better or equal to the ACP.
The obtained objective function and the required
computational time (on standard PC, Intel CPU
1,83 GHz, 2GB RAM) as a function of the vary-
ing regularization constant are presented in Ta-
ble 1. It is seen, that the GPPA algorithm consis-
tently attains more precise solution in a shorter
time. The average speedup was about 20, that is,
GPPA was more than an order of magnitude faster
compared to the ACP.
For completeness, we also report the training,
validation and test errors. For both algorithms
these errors differed on the forth decimal place
due to the tight stopping condition we used. Thus
the values in Table are valid for both methods.
The testing error for was 1,04 0,02.
The comparison of the approximated cutting
plane (ACP) algorithm and the proposed general-
ized proximal point algorithm (GPPA) on color
image segmentation problem. The better (smaller)
values of the upper bound on the optimal value
)( *F and the computation time are boldfaced. The
errors are percentage of misclassified pixels.
ACP of [5] Proposed GPPA
C )(UBF Time
[h:m:s]
),( F Time
[h:m:s]
TrnErr ValErr
0.01 20.6042 1:3:15 20.6018 0:7:31 3.26 2.69
0.05 50.7373 2:2:43 50.6869 0:11:5 1.93 1.06
0.10 72.9288 2:44:45 72.8832 0:12:34 1.71 0.98
0.50 197.7133 4:53:29 197.6659 0:14:48 1.11 0.09
1.00 327.7952 6:47:25 327.6003 0:19:26 1.09 0.87
5.00 1279.7376 10:15:56 1279.2701 0:21:4 0.98 0.99
27:47:33 1:26:28
7. Conclusions
We have shown that the learning of a general
Markov network can be expressed as a convex
optimization problem which is solvable efficiently
without calling any external max-sum solver. The
key idea of our LP-M3N formulation is to use the
Linear Programing relaxation of the max-sum
problem directly in the formulation of the Maxi-
34 УСиМ, 2011, № 2
mum Margin Markov Network learning algo-
rithm. The resulting LP-M 3 N problem can be
solved by a plethora of algorithms for non-smooth
optimization. We proposed a variant of the Gener-
alized Proximal Point Algorithm which is able to
solve large instances of the LP-M3N problem. The
empirical comparison demonstrates that our algo-
rithm speeds up the learning of general Markov
networks by a factor of up to 20 compared to the
Approximate Cutting Plane Algorithm, so far the
only existing learning algorithm for general
Markov Networks.
Acknowledgments
Vojtěch Franc was supported by the Czech
Ministry of Education project 1M0567 and by EC
projects FP7-ICT-247525 HUMAVIPS, PERG04-
GA-2008-239455 SEMISOL. Any opinions ex-
pressed in this paper do not necessarily reflect the
views of the European Community. The Commu-
nity is not liable for any use that may be made of
the information contained herein. Pavel Laskov
was supported by the Heisenberg Fellowship of
the German Science Foundation.
1. Altun Y., Hofmann T. Large Margin Methods for Label
Sequence Learning // Proc. of 8th Europ. Conf. on
Speech Communication and Technology, 2003.
2. Altun Y., Tsochantaridis I., Hofmann T. Hidden Markov
Support Vector Machines // Proc. of 20th Intern. Conf.
on Machine Learning, 2003.
3. Collins M. Discriminative Training Methods for Hidden
Markov Models: Theory and Experiments with Per-
ceptron Algorithms // Proc. of the Conf. on Empirical
Methods in Natural Lang. Proces., 2002.
4. Franc V. Optimization Algorithms for Kernel Methods
// PhD thesis, Czech Technical University, Karlovo
nám. 13, 12135, Prague, Czech Rep., July 2005.
5. Franc V., Savchynskyy B. Discriminative Learning of
Max-Sum Classifiers // J. of Machine Learning Re-
search. – Jan. 2008. – 9(1). – P. 67–104.
6. Koster A. Hoesel C.P.M. Kolen A.W.J. The Partial Con-
straint Satisfaction Problem: Facets and Lifting Theo-
rems // Operations Research Letters. – 1998. – 23(3–
5). – P. 89–97.
7. Medhi D. Ha C.D. Generalized Proximal Point Algo-
rithm for Convex Optimization // J. of Optimization The-
ory and Applications. – 1996. – 88(2). – P. 475–488.
8. Schlesinger M.I. Syntactic analysis of two-dimensional
visual signals in noisy conditions // Kibernetika. –
1976. – N 4. – P. 113–130. In Russian.
9. Schlesinger M.I., Flach B. Some solvable sublcasses
of structural recognition problems // Proc. of the Czech
Pattern Recognition Workshop, 2000. Czech Pattern
Recognition Society.
10. Schlesinger M.I., Giginyak V.V. Solving (max,+) prob-
lems in structural recognition using equivalent trans-
formations // Systems and machines for control. –
2007. – N 2. – P. 5–17. In Russian.
11. Schlesinger M.I., Hlaváč V. Ten lectures on statistical
and structural pattern recognition // Kluw. Acad. Publ.,
2002.
12. Taskar B. Learning Structured Prediction Models: A
Large Margin Approach. PhD thesis, Stanford Univ.,
2004.
13. Taskar B., Chatalbashev V., Koller D. Learning Asso-
ciative Markov Networks // Proc. of 21th Intern. Conf.
Machine Learning, 2004.
14. Taskar B., Guestrin C., Koller D. Maximum-margin
Markov Networks // Proc. of Neural Inform. Proces.
Syst., 2003.
15. Teo C.H., Vishwanathan S.V.N., Smola A., Quoc, V.Le.
Bundle Methods for Regularized Risk Minimization
// J. of Machine Learning Research. – 2010. – N 11. –
P. 311–365.
16. Wainwright M., Jaakkola T., Willsky A. MAP estima-
tion via agreement on hypertrees: message passing and
linear programming approaches // Conf. on Communi-
cation, Control and Computing, 2002.
17. Werner T. A Linear Programming Approach to Max-
sum Problem: A Review // IEEE Transactions on Pat-
tern Analysis and Machine Intelligence. – 2007. –
29(7).
© V. Franc, Center for Machine Perception, Department of
Cybernetics, Faculty of Electrical Engineering, Czech Techni-
cal University, Technická 2, 166 27 Prague 6, Czech Republic,
P. Laskov, Wilhelm-Schickard-Institut für Informatik, Sand 13,
72076 Tübingen, Germany, 2011
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|