M. Pawan Kumar













CCCP Algorithm for Latent Structural SVM

minw F(w) where F(w) = 1/2 ||w||2 + C/n Σi maxy,h{0, Δ(yi,y,h) - maxh* wT (Φ(xi, yi, h*) - Φ(xi, y, h))}

Here Φ(x, y, h) is the joint feature vector of the input, output and hidden variables. The user-specified function Δ(yi,y,h) measures the risk or loss between the ground-truth output y and the predicted output (y, h).

Inference step: Impute the hidden variables for each sample using the current estimate of the parameters wt. Specifically,

hi = argmaxh* wtT Φ(xi, yi, h*)

Update step: Keeping the value of the hidden variables fixed, update the parameters by optimizing F(w). Specifically,

wt+1 = argminw 1/2 ||w||2 + C/n Σi maxy,h{0, Δ(yi,y,h) - wT (Φ(xi, yi, hi) - Φ(xi, y, h))}

See [1] for a more detailed description of the CCCP algorithm for latent structural SVM.


[1] C.-N. Yu and T. Joachims. Learning structural SVMs with latent variables. In ICML, 2009.