www-ai.cs.tu-dortmund.de/LEHRE/SEMINARE/SS09/AKTARBEITENDESDM/LITERATUR/SchefferGraphsSVMstruct.pdf
LNAI 5211 - Exact and Approximate Inference for Annotating Graphs with Structural SVMs
between label and observation pairs,
$1(xi, yi) = (%k1,yi , . . . , %k|!|,yi) T ) &(xi),
and between neighboring labels,
$2(yi, yj) =
#
$% %k1,yi
... %k|!|,yi
&
'( )
#
$% %k1,yj
... %k|!|,yj
&
'( ,
where & is [...] other output ȳ in its decision function values by at least 1 ' )i:
.! i=1 f(x(i), y(i)) ' maxȳ $=y(i)f(x(i), ȳ) / 1 ' )i.
Optimization Problem 1 is solved iteratively by column generation: If at least one [...] ! k"V
%",$1(xk, yk)& + !
kl"E %",$2(yk, yl)&
5
! $"%
exp 4 !
k"V %",$1(xk, ȳ$
k )& + !
kl"E %",$2(ȳ$
k , ȳ$ l )&
5 (6)
=
exp
6 %",$1(xi, yi) +
! k"N (i)
%",$2(yk, yi)& 7
! $"%
exp
6 %",$1(xi,+) +
! …