QxRed

接下来看如何选择a_X
(1)的KKT条件：
w=C\sum_X \sum_Y a_X(Y)Δf(X,Y)
a_X(Y)>=0
\sum_Y a_X(Y)=1
a_X(Y)[Δt(X,Y)-ξ_X-w'Δf(X,Y)]=0
ξ_X>=Δt(X,Y)-w'Δf(X,Y) \forall Y

由最后一个条件
ξ_X>=max_Y`{Δt(X,Y`)-w'Δf(X,Y`)}
如果ξ_X>max_Y{Δt(X,Y)-w'Δf(X,Y)}，那么Δt(X,Y)-ξ_X-w'Δf(X,Y)!=0 \forall Y
由倒数第2个条件，a_X(Y)=0 \forall Y，但这又与\sum_Y a_X(Y)=1矛盾。
所以ξ_X=max_Y`{Δt(X,Y`)-w'Δf(X,Y`)}

a) a_X(Y)=0
此时,由
ξ_X>=Δt(X,Y)-w'Δf(X,Y)
=>max_Y`{Δt(X,Y`)-w'Δf(X,Y`)}>=Δt(X,Y)-w'Δf(X,Y)
=>max_Y`{w'f(X,Y`)+Δt(X,Y`)}>=w'Δf(X,Y)+Δt(X,Y)

b) a_X(Y)>0
此时由a_X(Y)[Δt(X,Y)-ξ_X-w'Δf(X,Y)]=0
=>ξ_X=Δt(X,Y)-w'Δf(X,Y)
=>Δt(X,Y)-w'Δf(X,Y)=max_Y`{Δt(X,Y`)-w'Δf(X,Y`)}
=>max_Y`{w'f(X,Y`)+Δt(X,Y`)}=w'Δf(X,Y)+Δt(X,Y)

记v(X,Y)=w'f(X,Y)+Δt(X,Y),v(X,!Y)=max_{Y`!=Y}{w'f(X,Y`)+Δt(X,Y`)}
这样
a)=> a_X(Y)=0 => v(X,Y)<=v(X,!Y)
b)=> a_X(Y)>0 => v(X,Y)>=v(X,!Y)

因此，对于每个X检测其上所有Y，如果不满足a)或者b)则取出X进行优化。但是Y有指数个，直接检测不可能。为此引入如下调整：
记
a_X(Y_T)=max_{Y`~Y_T}{a_X(Y`)}
v(X,Y_T)=max_{Y`~Y_T}{v(X,Y`)}
v(X,!Y_T)=max_{Y`!~Y_T}{v(X,Y`)}
T是(X,Y)中的一个clique

引入如下判别条件：
c) a_X(Y_T)=0 => v(X,Y_T)<=v(X,!Y_T)
d) a_X(Y_T)>0 => v(X,Y_T)>=v(X,!Y_T)

定理(Ben Taskar)：
a),b) 和 c) d)等价

其中a_X(Y_T),v(X,Y_T),v(X,!Y_T)可以通过viterbi求得
因此对于每个X,对于其上的所有可能的Y_T(一共是k*k*l个)，用viterbi求出a_X(Y_T),v(X,Y_T),v(X,!Y_T)，并用c), d)判别，如果不符合，则取出优化

选出X,Y`后，还需要选择Y``

i)如果 a_X(Y_T)=0 , v(X,Y_T)>v(X,!Y_T)
此时违反了c).c)和a)等价，假设Y`=max_{Y~Y_T}{a_X(Y)}. 则a_X(Y`)=0，表明f(X,Y`)不是一个support vector,但v(X,Y`)>v(X,!Y`)，即w'f(X,Y`)+Δt(X,Y`)>w'f(X,Y!=Y')+Δt(X,Y!=Y`) <=> Δt(X,Y`)-Δw'f(X,Y`)>Δt(X,Y!=Y`)-Δw'f(X,Y!=Y`) => Δt(X,Y`)-Δw'f(X,Y`)=ξ_X
这说明X,Y`是一个独一无二的support vector, a_X(Y`)应该为正(否则所有的a_X(Y)=0)。此时需要从别的a_X(Y)上移一些权重过来。因为\sum_Y a_X(Y)=1所以必定有a_X(Y)>0。因为a_X(Y`)=max_{Y~Y_T}{a_X(Y)},所以从其他a_X(Y_T`)中选择权重最大的那一个Y``=argmax_{Y~Y_T`,T`!=T}{a_X(Y)}

Y`=max_{Y~Y_T}{a_X(Y)}=>v(X,Y)>v_(X,!Y_T)   ???

ii)如果 a_X(Y_T)>0 , v(X,Y_T)<v(X,!Y_T)
假设Y`=max_{Y~Y_T}{a_X(Y)}。a_X(Y`)>0表明f(X,Y)是一个support vector，但v(X,Y_T)<v(X,!Y_T) => Δt(X,Y`)-Δw'f(X,Y`)<ξ_X
所以X,Y`不应该是一个support vector,因此a_X(Y`)需要减小，根据(4),所要找的Y``要满足v(X,Y``)>v(X,Y`)。而这个Y``一定存在，因为v(X,Y`)<v(X,!Y`)。由于v(X,Y_T)=v(X,Y`)=max_{Y~Y_T}{v(X,Y)},这样的Y``必须在!Y_T中找：Y``=argmax_{Y~Y_T`,T`!=T}{v(X,Y)}

总体流程如下：
1. 初始化: μ(X,Y_{i-1},Y_i)= (Y_{i-1},Y_i)==(t(X_{i-1}),t(X_i))
2. Set violation = 0
3. For each X
4.   For each Y_T in X
5.     calculate a_X(Y_T),v(X,Y_T),v(X,!Y_T) using viterbi algorithm
6.     if a_X(Y_T)=0 && v(X,Y_T)>v(X,!Y_T)
7.       violation = 1, Y_T`=Y_T, Y`=max_{Y~Y_T}{v(X,Y)}
8.       break
9.     else if a_X(Y_T)>0 && v(X,Y_T)<v(X,!Y_T)
10.      violation = 2, Y_T`=Y_T, Y`=max_{Y~Y_T}{a_X(Y)}
11.      break
12.    end
13.  if violation > 0
14.    break
15.end
16.if violation > 0
17.  For each Y_T != Y_T`
18.    if violation == 1 && a_X(Y_T)>0
19.      Y``= max_{Y~Y_T}{a_X(Y)}, break
20.    if violation == 2 && v_(X,Y_T)>v_(X,Y_T`)
21.      Y``= max_{Y~Y_T}{v(X,Y)}, break
22.  end
23.  δ`=optimize(a_X(Y`),a_X(Y``)) using (5)
24.  For each Y_{i-1},Y_i on Y`
25.    μ`(X,Y_{i-1},Y_i)=μ(X,Y_{i-1},Y_i)+δ`
26.  For each Y_{i-1},Y_i on Y``
27.    μ`(X,Y_{i-1},Y_i)=μ(X,Y_{i-1},Y_i)-δ`
28.  goto 3
29.end
30.return μ