QxRed

参考文献：
On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines

设训练集合S={(x1,y1),(x2,y2),...,(xm,ym)}. xi为观察值，yi为对应的类别标记。类个数为k。
支持向量机(SVM)分类器H_M是一个关于观察值的函数：
H_M(xi)=argmax_i M xi             (1)
M为该分类器的参数
对于某个观察值x(类标记y)来说，分类器的经验错误为
e(S,M,x)= H_M(x)!=y
分类器的经验错误为
e(S,M)=1/m \sum_x e(S,M,x)
由于计算量太大，直接求一个最小化经验错误e(S,M)的M是不可行的。为此，SVM所求的M是最小化经验错误的上界函数。对于(x,y)来说，经验错误的上界为：
e'(S,M,x)=max_r{Mr x+1-d(y,r)}-My x          (2)
其中 d(a,b)=1 if a=b, else =0
简单分析一下，
a)当\forall r!=y, My x>=Mr x+1时，由(1)，分类正确，e(S,M,x)=0;由(2)y=max_r{Mr x+1-d(y,r)} => e'(S,M,x)=0。 所以在这种情况下e'=e
b)当\forall r!=y, My x>=Mr x，且max_r{Mr x}+1>My x 时，由(1)，分类正确，e(S,M,x)=0;由(2)e(S,M,x)=Mr x+1-My x => 0<e'(S,M,x)=0<=1，所以此时e'(S,M,x)>=e(S,M,x)
c)当max_r{Mr x}>My x时，由(1)知，分类错误,e(S,M,x)=1，由(2)知，e'(S,M,x)=max_r{Mr x}+1-My x>1 => e'(S,M,x)>e(S,M,x)

所以\forall (x,y)  e'(S,M,x)>=e(S,M,x)
记e'(S,M)=1/m \sum_x e'(S,M,x)
可知，e'(S,M)>=e(S,M)，e'(S,M)为SVM所要最小化的上界函数：
M*=argmin_M e'(S,M)
SVM试图求一个M使得e'(S,M)=0
即：\forall i
max_r{Mr xi+1-d(yi,r)}-Myi xi = 0
即：\forall i,r
Myi xi+d(yi,r)-Mr xi >=1

同时，SVM要最小化泛化错误，因为泛化错误与||M||_2有关，所以SVM需要最小化||M||_2，这样就形成了SVM的目标函数：
min 1/2||M||_2^2
s.t. \forall i,r     Myi xi+d(yi,r)-Mr xi >=1
当S不是线性可分的时候，不存在M满足上面的不等式约束，为此引入松弛向量z>=0使得
Myi xi+d(yi,r)-Mr xi >=1-zi
这样就得到了新的SVM目标函数：
min 1/2 b||M||_2^2+\sum_i zi
s.t. \forall i,r     Myi xi+d(yi,r)-Mr xi >=1-zi       (3)
其中b>0是一个常数,\forall i, zi>=0这个约束隐含在上面的约束中：令r=yi就可以得到z>=0
(3)的对偶问题为：
max_h min_{M,z} L(M,z,h)=1/2 b||M||_2^2+\sum_i zi + \sum_{i,r}h_{i,r}[Mr xi+1-zi-Myi xi-d(yi,r)]
s.t. \forall i,r h_{i,r}>=0                            (4)
(3)是一个凸函数，因为目标函数为二次函数，而约束是线性不等式约束，且存在一个内点z->+\inf使得不等式严格成立，所以强对偶成立，(4)和(3)有相同的最优点
dL/dz=0 => \forall i, 1-\sum_{i,r}h_{i,r}=0 => \sum_r h_{i,r}=1            (5)
dL/dMr=0 =>
b Mr + \sum_i h_{i,r} xi - d[\sum_i Myi xi \sum_s h_{i,s}]/dMr = 0
=>b Mr + \sum_i h_{i,r} xi - \sum_{i,yi=r} xi = 0
=>b Mr + \sum_i h_{i,r} xi - \sum_i d(yi,r) xi =0
Mr=1/b [\sum_i( d(yi,r)-h_{i,r} )xi]                   (6)
将(6)(5)代入(4)，化简得到：
max_h Q(h)=-1/(2b)  \sum_{i,j} xi xj [\sum_r(d(yi,r)-h_{i,r})(d(yi,r)-h_{i,r})] - \sum_{i,r} h_{i,r}d(yi,r)         (7)

具体步骤：
由(4),
1/2 b||M||_2^2+\sum_i zi + \sum_{i,r}h_{i,r}[Mr xi+1-zi-Myi xi-d(yi,r)]
=1/2 b||M||_2^2 + \sum_i zi + \sum_{i,r}h_{i,r} Mr xi + \sum_{i,r}h_{i,r} - \sum_{i,r}h_{i,r}zi - \sum_{i,r}h_{i,r}Myi xi - \sum_{i,r}h_{i,r}d(yi,r)
=\sum_{i,r}h_{i,r} Mr xi - \sum_{i,r}h_{i,r}Myi xi + 1/2 b||M||_2^2 + (\sum_i zi - \sum_i zi \sum_r h_{i,r}) + (\sum_{i,r}h_{i,r} -  \sum_{i,r}h_{i,r}d(yi,r) )
=S1-S2+S3 + 0 + [m- \sum_{i,r}h_{i,r}d(yi,r)]
把(6)代入S1:
S1=\sum_{i,r}h_{i,r} Mr xi
  =\sum_{i,r}h_{i,r} xi 1/b [\sum_j( d(yj,r)-h_{j,r} )xj]
  =1/b \sum_{i,j} xi xj \sum_r h{i,r}(d(yj,r)-h_{j,r})
S2=\sum_{i,r}h_{i,r}Myi xi
  =\sum_{i,r}h_{i,r}xi 1/b \sum_j xj(d(yj,yi)-h_{j,yi})
  =1/b \sum_{i,j}xi xj \sum_r h_{i,r}(d(yj,yi)-h_{j,yi})
  =1/b \sum_{i,j}xi xj (d(yj,yi)-h_{j,yi})\sum_r h_{i,r}
  =1/b \sum_{i,j}xi xj (d(yj,yi)-h_{j,yi})
  =1/b \sum_{i,j}xi xj \sum_r d(yi,r)(d(yj,r)-h_{j,r})
S3= 1/2 b||M||_2^2
  = 1/2 b \sum_r Mr' Mr
  = 1/2 b \sum_r ( 1/b [\sum_i( d(yi,r)-h_{i,r} )xi] )(1/b [\sum_j( d(yj,r)-h_{j,r} )xj] )
  = 1/(2b) \sum_{i,j} xi xj \sum_r ( d(yi,r)-h_{i,r} )( d(yi,r)-h_{i,r} )
所以
S1-S2=-1/b \sum_{i,j}xi xj \sum_r[(d(yi,r)-h_{i,r})d(yj,r)-h_{j,r})]
S1-S2+S3=-1/(2b) \sum_{i,j} xi xj \sum_r ( d(yi,r)-h_{i,r} )( d(yi,r)-h_{i,r} )
Q(h)=-1/(2b) \sum_{i,j} xi xj \sum_r ( d(yi,r)-h_{i,r} )( d(yi,r)-h_{i,r} ) + [m- \sum_{i,r}h_{i,r}d(yi,r)]
由于求的是使得Q(h)最优的h*，所以加或者乘常数项不影响h*
所以h*=argmax_h Q'(h)=-1/(2b) \sum_{i,j} xi xj \sum_r ( d(yi,r)-h_{i,r} )( d(yi,r)-h_{i,r} )-\sum_{i,r}h_{i,r}d(yi,r)
即(7)式

记１i=第i行为1其他行为0的列向量。１为所有元素为1的列向量。ti=１yi-h_i则，
Mr=1/b \sum_i t_{i,r} xi         (8)
(7)式变为
max_t -1/2 \sum_{i,j} Kij(ti tj) + b\sum_i ti １yi
s.t.  \forall i ti<=１yi, ti１=0             (9)
其中，(7)乘了b，但这不影响t*, Kij=xi xj

SMO算法
通过数值方法，解出(9)。每次选取一个观察值xp进行优化
把(9)的目标函数表达成xp的多项式：
Q(tp)=-1/2 Kpp(tp tp)-1/2\sum_{i!=p,p}Kip(ti tp)-1/2\sum_{p,j!=p}Kpj(tp tj)-1/2\sum_{i!=p,j!=p)Kij(ti tj)+b tp １yp + \sum_{i!=p} ti １yi
=-1/2Kpp tp^2 -\sum_{i!=p,p}Kip(ti,tp)+b tp １yp + Cp
=-1/2Kpp tp^2 -[\sum_{i!=p}Kip ti-b１yp]tp + Cp
=-1/2Ap tp^2 - Bp tp + Cp
其中Ap,Bp,Cp都是与tp无关的常数
Bp=\sum_{i!=p}Kip ti-b１yp              (10)
这样，目标函数就变为：
tp*=min_tp 1/2 Ap tp^2 + Bp tp
s.t. tp<=１yp, tp１=0                    (11)
接着看看如何选这个xp，与两类SVM的SMO算法类似，选取最不符合KKT条件的那个。
(9)的对偶问题为
L(u,v,t) = min_{u,v} max_t -1/2 \sum_{i,j} Kij(ti tj) + b\sum_i ti １yi + \sum_{i,r}u_{i,r}(t_{i,r}-d(yi,r)) - v \sum_r t_{i,r}
s.t. u>=0
则第一个KKT条件为
dL/dt=0 =>
\sum_j Kij t_{j,r}-b d(yi,r)+u_{i,r}-vi=0
记F_{i,r}=\sum_j Kij t_{j,r}-b d(yi,r)  (*****)
=>F_i=\sum_j Kij tj - b１yi
=>F_i=\sum_{j!=i} Kji tj - b１yi + Kii ti
=>F_i=Bi+Kiiti                (参见(10))
=>F_{i,r}=B_{i,r}+Kii t_{i,r}          (12)
于是dL/dt=0 =>
F_{i,r} + u_{i,r}-vi=0  ,剩下的KKT条件为 (13)
u_{i,r}(t_{i,r}-d(yi,r))=0               (14)
u_{i,r}>=0                               (15)
t_{i,r}-d(yi,r)<=0                       (16)
\sum_r t_{i,r}=0                         (17)
对于(17)，类似于两类SMO，参数将在直线\sum_r t_{i,r}=0上优化，因此该条件在优化时用掉
下面将用(13)~(16)的充要条件来找出xp
由(15)(13)得：
F_{i,r}<=vi
a)t_{i,r}=d(yi,r),此时
F_{i,r}<=vi                              (18)
b)t_{i,r}<d(yi,r),此时
u_{i,r}=0=>F_{i,r}=vi => F_{i,r}<=vi, F_{i,r}>=vi   (19)
由(18)(19)得
max_r F_{i,r} <= vi <= min_{t_{i,r}<d(yi,r)} F_{i,r} (20)
显然max_r F_{i,r} >= max_{t_{i,r}<d(yi,r)} F_{i,r} >= min_{t_{i,r}<d(yi,r)} F_{i,r}
因此，phi_i=max_r F_{i,r}-min_{t_{i,r}<d(yi,r)} F_{i,r}>=0  (*)
所以p=argmin_i phi_i

找到需要优化的xp后，看看如何优化，这里去掉下标p
由(11)得到
t*=min_t 1/2 A t^2 + B t
=min_tp 1/2 A[t+B/A]'[t+B/A] + B'B/(2A)
=min_tp 1/2 A[t+B/A]'[t+B/A]
记w=t+B/A, D=B/A+１y                (**)
这样(11)就变为
min_w Q(w)=1/2 ||w||_2^2
s.t. w<=D, w'１=D'１-1              (21)
其对偶问题为
max_{a,θ} min 1/2 ||w||_2^2 + a'(w-D)-θ(w'１-D'１+1)
s.t. a>=0
其KKT条件为
dQ/dw=0 => w + a - θ=0 <=> w_r+a_r-θ=0  (22)
a>=0 <=> a_r>=0           (23)
w<=D <=>w_r <= D_r         (24)
a_r(w_r-D_r)=0              (25)
w'１=D'１-1                 (26)
由(23)(22),
w_r<=θ
由(24),
w_r<=min{θ,D_r}
由(23),当a_r=0时w_r=θ,
由(25),当a_r>0时w_r=D_r
所以
w_r=min{θ,D_r}               (***)
由(26)
\sum_r min{θ,D_r}=\sum_r D_r - 1
此时必定存在一个θ使得上式成立。因为左边是关于θ的单调连续增函数，当θ->-\inf时左边=-\inf,当θ->\inf时，左边=sum_r D_r>右边
利用θ+D_r=max{θ,D_r}+min{θ,D_r}，得到
\sum_r [θ+D_r - max{θ,D_r}] = \sum_r D_r -1
=> k θ = \sum_r max{θ,D_r} - 1
=> θ=1/k \sum_r max{θ,D_r} - 1/k   (****)
因此可以通过叠代的方法求出θ，论文中证明了，只要初始θ足够小，θ就可以通过
θ(l+1)=1/k \sum_r max{θ(l),D_r} - 1/k
叠代求得。因此选择θ(1)=min{D_r}得到
θ(2)=1/k \sum_r D_r - 1/k         (27)
这个初始值
补充一下：
这里的(26)相当于(17)，因此算法保证了整个优化过程在直线上进行

整个算法框架如下：
输入{(x1,y1)...(xm,ym)},k个类别
初始化
for i=1 to m
ti=0        (满足(17))
F_{i,r}=-b d(r,yi)   (r=1,..,k, 见(12)(10))
Ai=Kii

重复
a) 寻找需要优化的点：p=argmax_i phi_i
phi_i=max_r F_{i,r}-min_{t_{i,r}<d(yi,r)} F_{i,r}
  见(*)
b) 优化xp:
  初始化D_r=B_{p,r}/Ap+d(r,yp)=F_{p,r}/Ap-t_{p,r}+d(r,yp)
    见(10)(12)(**)
  θ(0)=1/k \sum_r D_r - 1/k
    见(27)
  由(****)叠代求解θ
  由(***)求出w,再由(**)求出t*
c) 更新F,t:
  Δt=t*-t
  for i=1 to m , r=1 to k
    F_{i,r}=F_{i,r}+Δt_{p,r} Kpi
     见(*****)
  t=t*
直到phi_i=0

输出
H(x)=argmax_r{Mr x}
    =argmax_r{\sum_i t_{i,r}(xi,x) }  (见(8))