0
$\begingroup$

(This is related to a question I asked a few days ago)

I've been through a few SVM derivations and the ones I follow are this Caltech lecture and this MIT lecture.

However, with both of them the Lagrangian they try to minimize is:

$$\mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\|\boldsymbol{w}\|^2 + \sum_i \alpha_i\left[y_i(\boldsymbol{w}^T\boldsymbol{x}+b)-1\right].$$

As opposed to: $$\mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\|\boldsymbol{w}\|^2 + \sum_i \alpha_i\left[y_i(\boldsymbol{w}^T\boldsymbol{x}+b)-1-s_i\right].$$

Where $s_i$ are the slack variables obtained from the inequalities: $$y_i(w^Tx + b) >= 1$$ Hence $$y_i(w^Tx + b) = 1 + s_i$$

Is it because when the inequality is not inactive all the Lagrange multipliers for it are going to be 0 and so we don't even consider them? If yes, then this bit from the Caltech lecture contradicts this statement

This implies that we will get the $\alpha_i$'s as zero but we shouldn't even be talking about them if we're not even considering the inactive equalities in the Lagrangian right.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

We have considered the inequality constraint.

If you introduce the slack variables, then we do not impose a sign constraint on $\alpha_i$ but we impose a sign constraint on $s_i \ge 0$.

If we do not introduce the slack variables (which is the common practice). We ends up with the sign constraint that $\alpha_i \ge 0$.

$\endgroup$
5
  • $\begingroup$ This raises more follow up questions in my head - (1) Does that mean that the constraint $\alpha >= 0$ doesn't hold for Lagrangians with equality constraints? I thought the $\alpha$'s were just proportionality constants that could be positive or negative? (2) Let's call Lagrange multipliers used when we introduce slack variables $\lambda$ and when we don't introduce slack variables $\alpha$, are you suggesting $\alpha 𝑦_𝑖(𝑤^𝑇𝑥_i+𝑏-1) = \lambda 𝑦_𝑖(𝑤^𝑇𝑥_i+𝑏-1-s_i)$ where $\alpha>=0$ and $s_i>=0$ $\endgroup$
    – GrowinMan
    Mar 3, 2019 at 7:16
  • $\begingroup$ If you introduce slack variable to make the inequality constraint becoming an equality constraint, and then we take the dual, there is no sign constraint on $\alpha_i$. At the optimal solution, from the complementary slackness condition we do have $\alpha_i y_i(w^Tx_i+b-1) = 0=\lambda_i y_i(w^Tx_i + b -1-s_i)$. $\endgroup$
    – Siong Thye Goh
    Mar 3, 2019 at 7:49
  • $\begingroup$ I understand what you're trying to say, but I'm having a really hard time convincing why it is true. I'd appreciate it if you could provide explanations/references for it. $\endgroup$
    – GrowinMan
    Mar 3, 2019 at 8:36
  • $\begingroup$ here is a note from stanford. Page 118 might help. $\endgroup$
    – Siong Thye Goh
    Mar 3, 2019 at 8:51
  • $\begingroup$ adding to this discussion: for purely linear problems it is trivial to show that the dual problems are equivalent, and it would not surprise me that you can also show that here. Have you tried to derive both duals to compare them? $\endgroup$
    – LinAlg
    Mar 3, 2019 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.