How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF?
Описан метод получения оптимальной размытой разметки по оптимальному решению двойственной задачи LP-релаксации на марковских случайных полях. Метод основан на LP-релаксации специального вида и алгоритме (max,+)-диффузии....
Gespeichert in:
| Datum: | 2011 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2011
|
| Schriftenreihe: | Управляющие системы и машины |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/82927 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? / T. Werner // Управляющие системы и машины. — 2011. — № 2. — С. 86-93. — Бібліогр.: 20 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-82927 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-829272025-02-23T17:52:38Z How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? Как находить решение прямой задачи LP-релаксации MRF по решению двойственной задачи ? Як обчислювати розв’язок прямої задачі LP-релаксації MRF за розв’язком двоїстої задачі ? Werner, T. Оптимизационные задачи структурного распознавания образов Описан метод получения оптимальной размытой разметки по оптимальному решению двойственной задачи LP-релаксации на марковских случайных полях. Метод основан на LP-релаксации специального вида и алгоритме (max,+)-диффузии. The method for computation of the optimal relaxed labeling from the optimal solution of a dual problem in the LP-relaxation of Markov Random Fields is described. The method is based on the particular form of the LP-relaxation and the (max,+)-diffusion algorithm. Описано метод отримання оптимальної розмитої розмітки за оптимальним розв’язком двоїстої задачі LP-релаксації на марківських випадкових полях. Метод базується на LP-релаксації спеціального типу і алгоритмі (max,+)-дифузії. This research has been supported by the European Community project FP7-ICT-247022 (MASH) and by the Czech government grant MSM6840770038. The author thanks Sebastian Nowozin for useful discussions. 2011 Article How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? / T. Werner // Управляющие системы и машины. — 2011. — № 2. — С. 86-93. — Бібліогр.: 20 назв. — англ. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82927 519.157 en Управляющие системы и машины application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Оптимизационные задачи структурного распознавания образов Оптимизационные задачи структурного распознавания образов |
| spellingShingle |
Оптимизационные задачи структурного распознавания образов Оптимизационные задачи структурного распознавания образов Werner, T. How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? Управляющие системы и машины |
| description |
Описан метод получения оптимальной размытой разметки по оптимальному решению двойственной задачи LP-релаксации на марковских случайных полях. Метод основан на LP-релаксации специального вида и алгоритме (max,+)-диффузии. |
| format |
Article |
| author |
Werner, T. |
| author_facet |
Werner, T. |
| author_sort |
Werner, T. |
| title |
How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? |
| title_short |
How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? |
| title_full |
How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? |
| title_fullStr |
How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? |
| title_full_unstemmed |
How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? |
| title_sort |
how to compute a primal solution from dual one in lp relaxation of map inference in mpf? |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2011 |
| topic_facet |
Оптимизационные задачи структурного распознавания образов |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/82927 |
| citation_txt |
How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF? / T. Werner // Управляющие системы и машины. — 2011. — № 2. — С. 86-93. — Бібліогр.: 20 назв. — англ. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT wernert howtocomputeaprimalsolutionfromdualoneinlprelaxationofmapinferenceinmpf AT wernert kaknahoditʹrešenieprâmojzadačilprelaksaciimrfporešeniûdvojstvennojzadači AT wernert âkobčislûvatirozvâzokprâmoízadačílprelaksacíímrfzarozvâzkomdvoístoízadačí |
| first_indexed |
2025-11-24T05:53:25Z |
| last_indexed |
2025-11-24T05:53:25Z |
| _version_ |
1849649901269417984 |
| fulltext |
86 УСиМ, 2011, № 2
UDC 519.157
T. Werner
How to Compute a Primal Solution from Dual One
in LP Relaxation of the MAP Inference in MRF ?
Описан метод получения оптимальной размытой разметки по оптимальному решению двойственной задачи LP-релаксации на
марковских случайных полях. Метод основан на LP-релаксации специального вида и алгоритме (max,+)-диффузии.
The method for computation of the optimal relaxed labeling from the optimal solution of a dual problem in the LP-relaxation of Markov Ran-
dom Fields is described. The method is based on the particular form of the LP-relaxation and the (max,+)-diffusion algorithm.
Описано метод отримання оптимальної розмитої розмітки за оптимальним розв’язком двоїстої задачі LP-релаксації на марків-
ських випадкових полях. Метод базується на LP-релаксації спеціального типу і алгоритмі (max,+)-дифузії.
Abstract
In the LP relaxation of MAP inference in Mar-
kov random fields (MRF), the primal LP maximi-
zes the MAP objective over relaxed labelings (pseu-
domarginals) and the dual LP minimizes an upper
bound on the true MAP solution by reparameteri-
zations. Having solved the dual LP, we have no
direct access to the corresponding primal solution.
We propose a simple way to compute an optimal
primal solution from an optimal dual solution.
Precisely, we give an algorithm that either shows
that the upper bound for a given problem can be
further decreased by reparameterizations (i.e., it is
not dual-optimal) or computes the corresponding
optimal relaxed labeling. This is done by first re-
moving inactive dual constraints and then solving
the resulting feasibility problem by a very simple
message-passing algorithm, sum-product diffusion.
The MAP inference in undirected graphical mo-
dels (Markov random fields, MRF) [16] leads to
the following NP-hard combinatorial optimization
problem: given a set of variables and a set of func-
tions of (small) subsets of the variables, maximize
the sum of the functions over all the variables.
The problem has a natural LP relaxation, proposed
independently in [15, 8, 16]. The primal task in
this LP relaxation maximizes the MAP objective
over relaxed labelings (pseudomarginals), the dual
LP minimizes an upper bound on the true MAP
solution by reparameterizations (equivalent trans-
formations) of the original problem.
Currently, the only known algorithms able to
compute the LP relaxation for large-scale instan-
ces are dual. Examples are algorithms based on ave-
raging max-marginals [10, 6, 4, 5], the Augmen-
ting DAG/VAC algorithm [9, 1], subgradient me-
thods [7, 14], or smoothing approaches [20, 17, 5, 12].
Having an optimal dual solution, it is not easy
to compute the corresponding primal solution (op-
timal relaxed labeling) for large-scale instances.
However, this primal solution can be sometimes
useful. In this paper, we present a simple algo-
rithm to compute an optimal primal solution from
an optimal dual solution in the LP relaxation. Pre-
cisely, suppose somebody gives us a problem and
claims it has the minimal upper bound among all
its reparameterizations. We want to either dis-
prove this claim or compute the corresponding pri-
mal optimum.
Given a dual solution, we first remove inactive
dual constraints, which means setting the corre-
sponding primal variables (pseudomarginals) to
zero. We are left with a feasibility task. This fea-
sibility task is replaced with its a smooth optimi-
zation task such that the primal optimum of the
smoothed task is a solution of the feasibility task.
The optimum of the smoothed task can be com-
puted with a very simple message passing algo-
rithm, which we call sum-product diffusion. If the
dual solution was not optimal, this is detected dur-
ing sum-product diffusion and a decreasing direc-
tion for the upper bound is provided.
We build our paper around the particular form of
the LP relaxation proposed in [15] and the max-
sum diffusion algorithm [10], which were reviewed
in [18]. Since researchers are most familiar with
problems with pairwise interactions, we present
our algorithm on these – but it can be straightfor-
wardly extended to the LP relaxation of problems
of an arbitrary order (arity), as proposed in [19, 3].
УСиМ, 2011, № 2 87
1. The MAP inference in MRF and its LP re-
laxation
Let V be a set of variables and
2
VE a set of
variable pairs, thus (V, E) is a graph. Variable u V
attains states xu from a finite domain Xu. An as-
signment (or labeling) is a tuple x X, where X is
the Cartesian product of the domains Xu for all
u V. We want to maximize the function
)],()([=)|( vuuv
Euv
uu
Vu
xxfxffxF
(1)
over all x X, where the functions
: [ , )u uf X and ),[: vuuv XXf
are given. All numbers )( uu xf and ),( vuuv xxf
form a single vector Tf ),[ , where
},,|),({
},|),({=
vvuuvu
uuu
XxXxEuvxxuv
XxVuxuT
denotes the set of all states of all the functions.
We understand E as an undirected graph, adopting
that ),(=),( uvvuvuuv xxfxxf . We will need also the
directed version E of E, such that for any undi-
rected edge uv E we have arcs in both directions
uv E and vu E.
Here are the primal (left) and the dual (right) of
the LP relaxation of the problem [15, 18]:
.)(min=,max
fUf (2)
In the primal, T[0,1] is the set of vectors
T[0,1] satisfying
uuuuvuuv
vx
XxEuvxxx ,,)(=),( * (3a)
( ) = 1 , .
u
u u
x
x u V (3b)
The set is often referred to as the local mar-
ginal polytope and the components of as pseu-
domarginals [16]. A vector is the collection
of distributions u and uv, subject to marginali-
zation constraints (3a) and normalization con-
straints (3b). In the scalar product ,f we de-
fine – ¥ 0 = 0.
The meaning of the dual can be understood by
combining two concepts, reparameterizations and
an upper bound on (1) , as shown next.
A reparameterization is a linear transformation
of vector f that preserves )|( fxF for all x X. The
simplest reparameterization is done as follows: pick
any uv E, subtract an arbitrary unary function
(usually called a «message») ),(: uuv X
from function fu and add it to function fuv:
( ) ( ) ( )u u u u uv uf x f x x (4a)
.)(),(),( uuvvuuvvuuv xxxfxxf (4b)
This preserves uvu ff and hence )|( fF . Ap-
plying to all *Euv yields
)()(=)( uuv
uNv
uuuu xxfxf
(5a)
,)()(),(=),( vvuuuvvuuvvuuv xxxxfxxf (5b)
where }|{= EuvvNu is the set of neighbors of
variable u. Vector is the collection of all the
numbers )( uuv x , thus f denotes the reparame-
terization of vector f by messages . Reparame-
terizations preserve not only )|( fF but also the
primal objective, i.e., for any we have
,=, ff .
The function U in the dual is an upper bound
on )|( fF ,
.)|(max
),(max)(max=)(
,
fxF
xxfxffU
Xx
vuuv
vxuxEuv
uu
uxVu
(6)
The meaning of the dual is now evident: it
minimizes the upper bound (6) by reparameteriza-
tions (5).
We will say that f is a dual optimum if it has
the least upper bound among all its reparameteri-
zations, i.e., U (f ) = min U (f
). Note that this is a
slight abuse of terminology because the decision
variables in the dual in (2) are rather than f.
1.1. The Relations between the primal and dual
The primal and dual are related by the well-
known duality theorems:
Weak duality: For any and any f, we
have )(, fUf .
Strong duality: For , we have , =f
= U (f ) if and only if is a primal optimum and f
is a dual optimum.
88 УСиМ, 2011, № 2
Complementary slackness: For , we
have )(=, fUf if and only if
[ ( ) ( )] ( ) = 0max u u u u u u
yu
f y f x x (7a)
,
[ ( , ) ( , )] ( ) = 0 .max uv u v uv u v uv uv
y yu v
f y y f x x x (7b)
If f is not a dual optimum then there exists no
satisfying (7).
1.2. Computing a primal solution as a feasi-
bility problem
Our task in this paper is to compute a primal
optimum from a dual optimum. More precisely,
somebody gives us a vector f and claims it has the
minimal upper bound among all its reparameteri-
zations, U (f ) = min U (f
). Our task is either to
disprove this claim or to compute such that
)(=, fUf .
Let us replace the given vector f [– , )T
with vector g {– , 0}T defined as
)(max=)(0
)(max<)(
=)(
uu
uy
uu
uu
uy
uu
uu yfxfif
yfxfif
xg , (8a)
.
),(max
=),(
0
),(max
<),(
=),(
,
,
vuuv
vyuy
vuuv
vuuv
vyuy
vuuv
vuuv
yyf
xxfif
yyf
xxfif
xxg (8b)
We assume that >)( fU , hence 0=)(gU .
Replacing f with g can be seen as removing inac-
tive dual constraints and setting the corresponding
primal variables to zero. This does not change our
task. Two cases can arise:
f is not a dual optimum: Clearly, f is a dual
optimum if and only if g is a dual optimum. Hence,
there exists such that U (g
) < 0. This is at
the same time a decreasing direction for U (f ), i.e.,
there exists 0> such that )(<)( fUfU ;
f is a dual optimum: Clearly, if f is a dual op-
timum then problems f and g have the same set of
optimal primal solutions. Hence, there exists
satisfying (7) , which is the desired primal
optimum. Condition (7) can be written in short as
0=, g , recalling that 0=0 .
Now, our task in this paper reduces to the fol-
lowing feasibility problem:
Problem 1 Given g {– , 0}T, find sa-
tisfying 0=, g . If such does not exist, find
such that 0<)( gU .
2. Solving the feasibility problem
Here we describe a solution to Problem 1. In
short, the idea is to replace task (2) with its smo-
othed version such that for g {– , 0}T, the pri-
mal optimum of the smoothed task is a primal op-
timum of the original task. The (dual and primal)
global optimum of the smoothed task can be com-
puted with a very simple message passing algo-
rithm.
Although the smoothed version of (2) will be
eventually applied to g {– , 0}T, we formulate
it for g [– , 0)T. It reads
.)(
~
min=,logmax
gUg (9)
The primal (left) can be understood as a mini-
mization of a convex free energy (here, maximiza-
tion of negative energy). In the dual (right), we have
)|(),(
)(=)(
~
,
gxFxxg
xggU
Xx
vuuv
vxuxEuv
uu
uxVu
(10)
where = log expi ii i
a a denotes the log-sum-exp
operation. The right-hand expression in (10) is the
log-partition function, hence U
~
is an upper bound
on the log-partition function. The bound is too
loose to be useful for approximating (log-) parti-
tion function but this is not our task here. The dual
is a differentiable convex task, it is at optimum if
)(=),( uuvuuv
vx
xgxxg (11)
holds for all *Euv and ux . The primal and dual
optima are related by
,
exp ( )
( ) = ,
exp ( )
exp ( , )
( , ) = .
exp ( , )
u u
u u
u u
xu
uv u v
uv u v
uv u v
x xu v
g x
x
g x
g x x
x x
g x x
(12)
УСиМ, 2011, № 2 89
We will not prove here the duality relation (9),
the inequality in (10), and the optimality condition
(11). This is easy and it can be found, e.g., in [20].
Plugging (12) into (11) verifies the marginaliza-
tion condition (3a), hence .
We can see that to solve the dual task in (9), we
need to reparameterize g to satisfy the stationary
condition (11). Then the primal solution can be
read off from (12).
Note, the approach has the desirable property
that pseudomarginals need not be explicitly
stored in the memory, they are given implicitly by
(11). Therefore we need to store only unary func-
tions rather than unary and binary functions .
2.1. The enforcing arc consistency
It can happen that the condition (11) is impos-
sible to satisfy by any choice of . This is because
reparameterizations cannot change a finite weight
to an infinite one or vice versa (note, messages
cannot take infinite values) – in other words,
>)( uu xg if and only if >)( uu xg , and
similarly for guv. Therefore, the finite part of g has
to satisfy the property known as arc consistency
[2]: for all uv E and xu we have
]>)(>),(max[ uuvuuv
vx
xgxxg . (13)
Polynomial algorithms exist that recursively set
some of the weights g to until g becomes arc
consistent. This is known as a relaxation labeling
[13] or, in constraint satisfaction, as an enforcing
arc consistency or a constraint propagation [2]. It
is outlined in Algorithm 1.
Algorithm 1. Enforcing arc consistency.
1: repeat;
2: Find uv E and xu violating (13).
3: )( uu xg
4: ),( vuuv xxg for all xv
5: until no change is possible
It can be shown that enforcing arc consistency
does not change the optimum of (9). In particular,
if Algorithm 1 sets all weights to ( =g ),
Problem 1 is infeasible.
2.2. A message passing algorithm
The dual in (9) can be solved by coordinate de-
scent, which leads to a message passing algorithm.
The algorithm repeats the following iteration until
convergence:
Pick any uv E and enforce equality (11) by
reparameterization (4).
This strictly monotonically decreases )(
~ gU .
On convergence, (11) holds globally.
Algorithm 2. The ),( -diffusion algorithm.
1: repeat;
2: for *Euv and uu Xx >)( uu xg do
3:
),()(
2
1
)()(
vuuv
vx
uu
uuvuuv
xxgxg
xx
4: end for
5: until convergence
This is summarized in the Algorithm 2. It is pre-
cisely analogical to max-sum diffusion [10, 18],
only the function max was replaced with the log-
sum-exp function . The algorithm assumes that g
is arc consistent – then, the condition >)( uu xg
ensures that )( uuv x is never set to or .
2.3. Solving the feasibility problem
Let us put things together and see how to solve
Problem 1. For Tg ,0}{ , any satisfying
>,logg satisfies also 0=, g . Hence,
any feasible to the primal in (9) solves Problem 1.
For any g we have )()(
~
gUgU because the
log-sum-exp function upper bounds the maxi-
mum, i ai maxi ai, Hence, if during the Algo-
rithm 2 we get 0<)(
~ gU , it implies 0<)( gU .
Thus, Problem 1 is solved as follows:
1. Enforce arc consistency, Algorithm 1. If
=g , stop (Problem 1 is infeasible);
2. Run Algorithm 2. If 0<)(
~ gU any time dur-
ing the algorithm, stop (Problem 1 is infeasible);
3. Otherwise, let Algorithm 2 converge and
then compute a solution of Problem 1 from (12) .
Before the convergence of Algorithm 2, given
by (17) satisfies 0=, g but violates the mar-
ginalization constraint (3a). On convergence,
satisfies (3b), hence .
90 УСиМ, 2011, № 2
a b
Fig. 1. The depicted reparameterization decreases edge e to an
arbitrarily small value
2.4. Unbounded messages
The algorithm has an interesting but undesired
property: even if problem the (9) is bounded, its
optimum may be attained for . In that
case, during the Algorithm 2 some of the messa-
ges )( uuv x will diverge to or .
Fig. 1, a shows an example of this phenome-
non. It shows a problem with 3=V variables, the
complete graph E, and 2|=| uX labels. All the
nodes have weights 0=)( uu xg . The shown edges
have weights 0=),( vuuv xxg , the remaining (not
shown) edges have weights =),( vuuv xxg .
Consider the reparameterization given by
setting =)( uuv x for the six messages depicted
by dashes, and 0=)( uuv x for the remaining six
messages. For any , this reparameterization
changes the weight of edge e to =)(eg and
leaves the remaining weights unchanged. For any
0 , we have =)( gU ( ) = 0U g . By comple-
mentary slackness, it necessarily follows that
0=)(e .
Although the bound )( gU is the same for any
0 , the smoothed upper bound )(
~ gU de-
creases with increasing . Since Algorithm 2
minimizes )(
~ gU , it will keep increasing (and
hence decreasing )(eg ) without any limits. This
must be so because by (12), for 0=)(e we need
=)(eg .
This behavior can lead to numerical problems
because in (5) we can get expressions like
),(=),( vuuvvuuv xxgxxg where is a very
large number. This can be alleviated by doing re-
parameterizations (1) «in-place» by directly chang-
ing g (Algorithm 3) rather than by storing mes-
sages – but in that case we may instead have prob-
lems with error accumulation. Moreover, modify-
ing binary functions ),( uvg typically needs more
memory than storing only unary functions )(uv .
Algorithm 3. The ),( -diffusion algorithm,
message-free version.
1: repeat;
2: for *Euv and uu Xx such that
>)( uu xg do
3: )],()([
2
1
vuuv
vxuu xxgxg
4: )()( uuuu xgxg
5: ),(),( vuuvvuuv xxgxxg for all vx
6: end for
7: until convergence
The phenomenon can be further clarified as fol-
lows. Let two vectors Tgg ),[, be called
equivalent if they define the same function )|( gF .
An equivalent transformation is a change of vec-
tor g to its equivalent. Now, three classes of equiva-
lent transformations can be distinguished [20]:
1. Transformations that are compositions of a
finite number of local reparameterizations (4).
These are precisely the linear transformations (5).
2. Transformations that are compositions of an
infinite number of local reparameterizations (4).
The resulting transformations are not all covered
by (5) because (5) does not allow to change a fi-
nite weight to or vice versa.
3. Transformations that are not compositions
of any number of local reparameterizations (4).
E.g., any unsatisfiable CSP is equivalent to the
empty CSP.
The problems in Figure 1 (a) and 1 (b) are equi-
valent in the second sense. Hence, there exists no
that would reparameterize Figure 1 (a) to Fig-
ure 1 (b) or vice versa.
2.5. A sum-product version of the algorithm
The Algorithms 2 and 3 require a time-consu-
ming evaluation of the log-sum-exp function. By
applying the exponential function to all involved
УСиМ, 2011, № 2 91
quantities, these algorithms (and the theory in § 2)
can be translated from the semiring ),),,([
into the sum-product semiring ),),([0, . Then,
the algorithms will use only addition, multiplica-
tion, division, and square root. We refer to the re-
sulting algorithm as sum-product diffusion. Its
message-free version is Algorithm 4. Its input is a
vector g [0, )T that is assumed to be arc con-
sistent, i.e., 0>),(max vuuvvx xxg if and only if
0>)( uu xg .
Algorithm 4. The sum-product diffusion algo-
rithm, message-free version.
1: repeat;
2: for *Euv and uu Xx such that
>)( uu xg do
3: 1/2)],()/([ vuuv
vxuu xxgxg
4: )/()( uuuu xgxg
5: ),(),( vuuvvuuv xxgxxg for all vx
6: end for
7: until convergence
In the sum-product form, the core idea of our
paper is especially obvious. Inequality (10) reads
,)|(
),()(=)(
~
,
gxF
xxgxggU
Xx
vuuv
vxuxEuv
uu
uxVu
(14)
where
.),()(=)|( vuuv
Euv
uu
Vu
xxgxggxF
(15)
The stationary condition (11) reads
.)(=),( uuvuuv
vx
xgxxg (16)
Now, the problem 1 is solved simply by apply-
ing sum-product diffusion to g {0, 1}T. It is ob-
vious that after convergence, the optimal coin-
cides with g (up to normalization) – because (16)
is the marginalization condition (3a) we want to
impose.
Moreover, the test for infeasibility of Prob-
lem 1 has an interesting interpretation in terms of
the constraint satisfaction problem (CSP) [11]. A
vector g {0, 1}T can be understood as a (pair-
wise) CSP, the functions gu : Xu {0, 1} and
{0,1}: vuuv XXg representing unary and bi-
nary relations. A solution of the CSP is an as-
signment Xx satisfying all the relations, i.e.,
1=)|( gxF . The CSP is satisfiable if it has at least
one solution.
For g {0, 1}T, the right-hand side of inequal-
ity (14) is the number of solutions of the CSP.
This is known as the counting constraint satisfac-
tion problem (#CSP). Thus, )(
~
gU is an upper
bound on the number of solutions of the CSP.
This bound is too loose to be useful, except in one
situation: 1<)(
~
gU implies that the CSP is unsat-
isfiable. Algorithm 4 minimizes )(
~
gU by re-
parameterizing g, hence preserving )|( gF . If any
time during the algorithm we get 1<)(
~
gU , we
know that the CSP is unsatisfiable. Therefore,
sum-product diffusion provides a test to disprove
satisfiability of a CSP. This test is dissimilar to all
tests based on local consistencies [2], used in con-
straint programming. However, note that it is not
apparent at the first sight that this test is equiva-
lent to satisfiability of the Problem 1 – to show
this, we needed the duality relation (9) .
3. What about non-optimal dual solutions?
Many algorithms to tackle the dual in (2) yield
only suboptimal dual solutions f – most impor-
tantly, the algorithms based on the averaging max-
marginals, such as max-sum diffusion [10, 18] or
TRW-S [6]. An example of a problem that is a
fixed point of these algorithms but is not a dual
optimum is in Fig. 2. In that case, Algorithm 2
does not converge and achieves 0<)(
~ gU .
Therefore, it would be useful to compute a subop-
timal primal solution from a suboptimal dual solu-
tion. We do not know how to modify our algo-
rithm in a principled way to achieve this. But one
can think of several heuristics.
Of the duality relations (§ 1.1), one can sacri-
fice either primal feasibility or zero duality gap. One
option is to minimize primal infeasibility (viola-
tion of (3a) ) subject to zero duality gap – but we
do not know how to do this for large instances.
92 УСиМ, 2011, № 2
Fig. 2. An example of a fixed point of max-sum diffusion (or TRW-S)
that is not a dual optimum (given by Schlesinger [18])
However, our algorithm can be modified to find a
feasible primal solution with possibly small (but
in general not minimal) duality gap. Instead of (8),
let g be defined by
)(max)(0
)(max<)(
=)(2
uu
uy
uu
uu
uy
uu
uu yfxfif
yfxfif
xg (17a)
),(max
),(
0
),(max
<),(
=),(
,
,
vuuv
vyuy
vuuv
vuuv
vyuy
vuuv
vuuv
yyf
xxfif
yyf
xxfif
xxg . (17b)
For any 0 and > 0, the Algorithm 2 will
converge (with either sign of )(
~ gU ) and (12)
will be a feasible primal solution . With a
small and large , one can expect a reasonably
small duality gap ,)( ffU . Unfortunately,
this cannot be guaranteed based on solely and
because for unbounded weights g the gap can be un-
bounded in general. Currently, we cannot provide
a bound on the duality gap based on , and g.
4. Conclusion
We have proposed an algorithm to compute a
primal optimal solution from an optimal dual solu-
tion in the LP relaxation of MAP-MRF inference.
If the dual solution is not optimal, we provide a
decreasing direction as a certificate of non-
optimality. The main idea of our approach is ex-
tremely simple, in fact being summarized by
§ 2.5. We have discussed an interesting but unde-
sirable behavior of the algorithm, unbounded mes-
sages.
In this paper, we do not provide enough empi-
rical evidence that our approach is useful in prac-
tice. We tested the algorithm on instances with a
sparse (grid) graph E and random weights f drawn
i.i.d. from the normal distribution. Dual solutions
were obtained by the max-sum diffusion. For the in-
stances with V = 202 variables, the dual solution was
optimal in approx. 50% cases, for the instances with
V = 502 variables almost never. For optimal dual so-
lutions, optimal primal solutions could always be
found up to a small primal infeasibility. Unboun-
ded messages never caused a serious problem.
We formulated the algorithm for one particular
form of the LP dual [15, 18], closely related to max-
sum diffusion [10, 18]. However, it can be easily
extended to algorithms with tree-based updates, both
using the max-marginal averaging [6] and subgra-
dients [7, 14]. In that case, the problem g would
have to be defined in a different way than by (8).
Acknowledgment
This research has been supported by the Euro-
pean Community project FP7-ICT-247022
(MASH) and by the Czech government grant
MSM6840770038. The author thanks Sebastian
Nowozin for useful discussions.
1. Soft arc consistency revisited / M. Cooper, S. de Givry,
M. Sanchez, T. Schiex, M. Zytnicki, T. Werner // Arti-
ficial Intelligence. – 2010. – 174(7–8). – P. 449–478.
2. Debruyne R., Bessiиre Ch. Domain Filtering Consis-
tencies // J. of Artificial Intelligence Research. – 2001. –
14. – P. 205–230.
3. Franc V., Sonnenburg S., Werner T. Cutting Plane
Methods in Machine Learning / S. Sra, S. Nowozin,
S.J. Wright, ed. // Optimization for Machine Learning.
MIT Press, 2011.
4. Globerson A., Jaakkola T. Fixing Max-Product: Con-
vergent Message Passing Algorithms for MAP LP-
Relaxations // Neural Inform. Proc. Syst. (NIPS). –
2008. – P. 553–560.
5. Johnson J. Malioutov D.M., Willsky A.S. Lagrangian rela-
xation for MAP estimation in graphical models // Al-
lerton Conf. Communication, Control and Computing,
2007.
6. Kolmogorov V. Convergent Tree-Reweighted Message
Passing for Energy Minimization // IEEE Trans. Pat-
tern Analysis and Machine Intelligence. – 2006. –
28(10). – P. 1568–1583.
7. Komodakis N., Paragios N., Tziritas G. MRF Optimi-
zation via Dual Decomposition: Message-Passing Re-
visited // Intl. Conf. Computer Vision (ICCV), 2007.
УСиМ, 2011, № 2 93
8. Koster A., van Hoesel C.P.M., Kolen A.W.J. The Par-
tial Constraint Satisfaction Problem: Facets and Lifting
Theorems // Operations Research Letters. – 1998. –
23(3–5). – P. 89–97.
9. Koval V.K., Schlesinger M.I. Two-dimensional Program-
ming in Image Analysis Problems // Automatics and
Telemechanics. – 1976. – 8. – P. 149–168. In Russian.
10. Kovalevsky V.A., Koval V.K. A diffusion algorithm for
decreasing the energy of the max-sum labeling prob-
lem. Glushkov Institute of Cybernetics, Kiev, USSR.
Unpublished, approx. 1975.
11. Mackworth A. Constraint Satisfaction // Encyclopaedia
of Artificial Intelligence, Wiley, 1991. – P. 285–292.
12. Ravikumar P., Agarwal A., Wainwright M.J. Message-
passing for Graph-structured Linear Programs: Proxi-
mal Methods and Rounding Schemes // J. of Machine
Learning Research. – 2010. – 11. – P. 1043–1080.
13. Rosenfeld A., Hummel R.A., Zucker S.W. Scene Label-
ing by Relaxation Operations// IEEE Trans. on Syst.,
Man, and Cybernetics. 1976. – 6(6). – P. 420–433.
14. Schlesinger M.I., Giginjak V.V. Solving (max,+) Prob-
lems of Structural Pattern Recognition Using Equivalent
Transformations // USiM (Control Systems and Ma-
chines). – 2007. – N 1,2. In Russian, English transla-
tion available on www.irtc.org.ua/image/publications.
15. Schlesinger M.I. Syntactic analysis of two-dimensional
visual signals in noisy conditions // Cybernetics and
Systems Analysis. – 1976. – 12(4). – P, 612–628.
Translation from Russian.
16. Wainwright J., Jordan M.I. Graphical Models, Expo-
nential Families, and Variational Inference // Foundations
and Trends in Machine Learning. – 2008. – 1(1–2). –
P. 1–305.
17. Weiss Y., Yanover Ch., Meltzer T. MAP Estimation, Line-
ar Programming and Belief Propagation with Convex
Free Energies // Conf. Uncertainty in Artificial Intelli-
gence (UAI), 2007.
18. Werner T. A Linear Programming Approach to Max-
sum Problem: A Review // IEEE Trans. Pattern Analy-
sis and Machine Intelligence. – July 2007. – 29(7). –
P. 1165–1179.
19. Werner T. Revisiting the Linear Programming Relaxa-
tion Approach to Gibbs Energy Minimization and Wei-
ghted Constraint Satisfaction // Ibid. – August 2010.
20. Werner T., Shekhovtsov A. Unified Framework for Semi-
ring-Based Arc Consistency and Relaxation Labeling
// 12th Computer Vision Winter Workshop, 2007. –
P. 27–34. – St. Lambrecht, Austria, Graz University of
Technology.
© T. Werner, A Center for MachinePerception, Czech Technical
University, Prague, 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
|