Chun-Nam John Yu, Joachims , Learning structural SVMs with latent variables 2009

Citation

Chun-Nam John Yu and Thorsten Joachims. Learning structural SVMs with latent variables. In Proceedings of the 26th International Conference on Machine Learning,Montréal, Québec, Canada, 2009.

Online version

[1]

Summary

In this paper author talks about the use of latent variable in the structural SVM. The paper also identifies the formulation for which their exists effecient algorithm to find the local optimum using convex-concave optimization techniques. The paper argues that this is the first time latent variable are being used in large margin classifiers.Experiments were then performed in various domains of computational Biology, IR and NLP to prove the generality of the proposed method.

Method Used

This paper extends the formulation of Structured SVM given by Tsochantaridis to include a latent variable in it.

Consider set of Structed input out put pairs $S={(x1,y1),.......(xn,yn)}\epsilon (XxY)^{n}$

The prediction rule comes as Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f_{w}(x)=argmax_{y\epsilon Y}[w.G(x,y)]}

where G is the joint feature vector that describes the relation between input and output.This paper introduces an extra latent variable h so now the prediction rule will be

$f_{w}(x)=argmax_{(y,h)\epsilon YxH}Y[w.G(h,x,y)]$

Similary extending the loss function $\triangle$ to include latent variable will be: Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \triangle ((y_{i},h_{i}^{*}(w)),(y_{i}^{o}pt(w),hi^{o}pt(w)))}

         where
            Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle h_{i}^{*}(w)=argmax_{h_{\epsilon }H}w.G(x_{i},y_{i},h)}

             
           Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle  (y_i^opt(w), hi^optopt(w)) = argmax_{(y,h) \epsilon YxH}w.G(x_i,y,h) }

Loss function is the difference between the pair given by prediction rule and the latent variable Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h_i^* } which explains the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (X_i, Y_i) }

Like in the case of structural svm we can derive the upper bound of this function maximizing over y and h.It further assumes that loss function does not depend upon the latent variable for the tasks in considerations. The final objective function comes as

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle  min_w[1/2||w^2|| + C\sum\limits_{s=1}^{n} max_{y^o,h^o \epsilon (YxH)} [w.G(x_i,y^o,h^o)+ \triangle(yi,y^o,h^o)]] - [C\sum\limits_{s=1}^{n} max_{h \epsilon H} w.G(x_i,y_i,h)] }

This objective function is the difference of two convex functions , so it can be soved using Concave Convex procedure given below

1. 1.Set t = 0 and initialize Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_0 }
2. 2 repeat
   1. Find Hyperplane vt such that -g(w) <= -g(wt) +(w-wt).vt for all w
   2. Solve wt+1 = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{t+1} = argmin{w}f(w) + w.v_t}
   3. t=t+1
3. until Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [f(w_t) - g(w_t)] - [f(w_{t-1} - g(w_{t-1})] < \epsilon }

The paper claims that above algorithm is guaranteed to converge.

Experimentation

The experimentations were performbed in many domains and results were as follows

Discriminative Motif finding

Error rate : Gibbs sampler 32.49% Latent Structural SVM 12%

Noun Phrase Coreference via Clustering

MITRE Loss: SVM cluster 41.3 Latent SVM 35.6

The Structural SVM with latent variable also perform well in the task of Document Retrieval and outperformed List NET and Ranking SVM.