How to select joint feature representation for structural SVM with binary loss?

Question

For using structured SVM with binary loss one needs to define a combined feature representation $\psi(x, y)$ of inputs $x$ and output $y$. For binary output $y \in \{-1, 1\}$.

While computing the most violated constraint we maximize the loss augmented score over $y$, i.e, $max_{y} \Delta(y, y_i) + w^T.\psi(x, y)$ where $\Delta()$ is 0-1 loss and $y_i$ is the the ground truth.

My doubt is how does one select the right $\psi()$. I have seen some people use $\psi(x, y) = x.y/2$ and some use $\psi(x, y) = x.y$. But the selection of the most violated constraint shouldn't get affected by the choice of $\psi()$. For example, if $\psi()$ is defined as say $1000*x.y$, then the selection of the most violated constraint would be dominated just by the second term and the loss term would be ignored. Any ideas, am I missing something?

Answer 1

Tsochantaridis et. al. discuss this problem in "Large Margin Methods for Structured and Interdependent Output Variables."

They compare a number of structured max-margin formulations and observe that the "slack rescaling" formulation is scale invariant while the "margin rescaling" formulation is not (Section 2.2.5). So the $\Delta(y_i,y)$ function in margin scaling formulation does need to be adjusted according to the scaling of the feature function.

Feature function scaling, though, is probably not a real problem in practice because the feature function is usually used to decompose a large output space and wouldn't be used to hide arbitrary scaling factors.

The factor of $.5$ that you mention may be due to mapping the standard two-class svm formulation to the structured formulation. The feature mapping portion of the constraint in the structured problem can be written as:

$$ w_{y_i} \cdot \Psi(x,y_i) - w_{\neg y_i} \cdot \Psi(x,\neg y_i)\\ \quad=(w_{y_i} \cdot x) y_i - (w_{\neg y_i} \cdot x) \neg y_i\\ \quad=(w_{y_i} + w_{\neg y_i}) \cdot x \; y_i $$

If you assume that $w_{y_i}=w_{\neg y_i}$ and the equivalent regularizer from the standard 2-class svm is $||w||^2\dot = ||w_{y_i} + w_{\neg y_i}||^2$, then this would penalize the weights twice as much as the structured regularizer, $||w_{y_i}||^2 + ||w_{\neg y_i}||^2$. Hence, you would want the value of the structured constraint to be $(w_{y_i} + w_{\neg y_i}) \cdot x\;y_i/2\ge 1$ (if you assume a 0-1 loss).