1
$\begingroup$

EDIT: The terms at the end will not get cancelled as they involve different variables: $\alpha$ and $\alpha^*$, etc. Now the post is corrected. I will leave this question here in case someone is as dummy as me and finds this post in the future.

I am trying to derive SVM regression model step by step in order to understand it better. However there is one step I cannot understand at all: the moment in which the primal formulation is switched to dual formulation and the minus sign appears in front of a term. The Lagrange primal function that is to be minimized is given as follows:

$$L=\frac{1}{2}\lVert \textbf{w} \rVert^2 + C \sum_{i=1}^{p}(\xi_i+\xi^*)-\sum_{i=1}^{p}(\eta_i\xi_i+\eta_i^*\xi^*)+\\-\sum_{i=1}^{p}\alpha_i(\varepsilon+\xi_i-y_i+\langle\textbf{w},\textbf{x}_i\rangle+b)+\\-\sum_{i=1}^{p}\alpha_i^*(\varepsilon+\xi_i^*+y_i-\langle\textbf{w},\textbf{x}_i\rangle-b)$$ with $\alpha_i,\alpha_i^* \geq0$ and $\eta_i,\eta_i^* \geq0$ and $p$ being the size of the dataset.

And then the dual formulation is given: $$\max_{\alpha, \alpha^*} \left[ \sum_{i=1}^{p}y_i(\alpha_i-\alpha_i^*)-\varepsilon\sum_{i=1}^{p}(\alpha_i+\alpha_i^*) \color{red}-\frac{1}{2}\sum_{i=1}^{p}\sum_{j=1}^{p}(\alpha_i-\alpha_i^*)(\alpha_j-\alpha_j^*)\langle\textbf{x}_i,\textbf{x}_j\rangle \right]$$ subject to $\sum_{j=1}^{p}(\alpha_i-\alpha_i^*)=0$ and $\alpha_i,\alpha_i^* \in[0,C]$.

The problem I have is the minus sign (marked red) preceeding the last term. I've derived the formula many times and I always get the plus sign before it. I guess there is some trick with switching from primal to dual formulation which I am not aware of.

I've checked that in multiple sources (for example A Tutorial on Support Vector Regression) and five books on ML I have and still found no answer. I've found a great post on the problem of classification on Cross Validated. However it did not help me to solve my problem.

My derivation is given below (skipping the derivation of the primal problem since I've got the same outcome):

  • the derivatives of $L$ with respect to primal variables are: $$\frac{\partial L}{\partial \textbf{w}}=w-\sum_{j=1}^{p}(\alpha_i-\alpha_i^*)x_i=0$$ $$\frac{\partial L}{\partial b}=\sum_{j=1}^{p}(\alpha_i^*-\alpha_i)=0$$ $$\frac{\partial L}{\partial \xi}=C-\alpha_i-\eta_i=0$$ $$\frac{\partial L}{\partial \xi^*}=C-\alpha_i^*-\eta_i^*=0$$

  • Introducing $C-\alpha_i-\eta_i=0$ and $C-\alpha_i^*-\eta_i^*=0$ into $-\sum_{i=1}^{p}(\eta_i\xi_i+\eta_i^*\xi^*)$ yields $$-C\sum_{i=1}^{p}(\xi_i+\xi_i^*)+\sum_{i=1}^{p}\alpha_i\xi_i+\sum_{i=1}^{p}\alpha_i^*\xi_i^*$$ step-by-step: $-\sum_{i=1}^{p}(\eta_i\xi_i+\eta_i^*\xi^*)=-\sum_{i=1}^{p}\eta_i\xi_i-\sum_{i=1}^{p}\eta_i\xi_i=-\sum_{i=1}^{p}(C-\alpha_i)\xi_i-\sum_{i=1}^{p}(C-\alpha_i^*)\xi_i^*=$ $-C\sum_{i=1}^{p}\xi_i+\sum_{i=1}^{p}\alpha_i\xi_i-C\sum_{i=1}^{p}\xi_i^*+\sum_{i=1}^{p}\alpha_i^*\xi_i^*=$ $-C\sum_{i=1}^{p}(\xi_i+\xi_i^*)+\sum_{i=1}^{p}\alpha_i\xi_i+\sum_{i=1}^{p}\alpha_i^*\xi_i^*$

  • Expanding $$\sum_{i=1}^{p}\alpha_i(\varepsilon+\xi_i-y_i+\langle\textbf{w},\textbf{x}_i\rangle+b)=\\ \varepsilon\sum_{j=1}^{p}\alpha_i+\sum_{i=1}^{p}\alpha_i\xi_i-\sum_{i=1}^{p}\alpha_i y_i+\sum_{i=1}^{p}\alpha_i \langle\textbf{w},\textbf{x}_i\rangle+b\sum_{i=1}^{p}\alpha_i$$ and $$\sum_{i=1}^{p}\alpha_i^*(\varepsilon+\xi_i^*+y_i-\langle\textbf{w},\textbf{x}_i\rangle-b)=\\ \varepsilon\sum_{j=1}^{p}\alpha_i^*+\sum_{i=1}^{p}\alpha_i^*\xi_i^*+\sum_{i=1}^{p}\alpha_i^* y_i-\sum_{i=1}^{p}\alpha_i^* \langle\textbf{2},\textbf{x}_i\rangle-b\sum_{i=1}^{p}\alpha_i^*$$

  • Using the fact that $\lVert \textbf{w} \rVert^2=\sum_{i=1}^{p}\sum_{j=1}^{p}(\alpha_i-\alpha_i^*)(\alpha_j-\alpha_j^*)\langle\textbf{x}_i,\textbf{x}_j\rangle$ and introducing all above to the $L$ i get: $$\frac{1}{2}\sum_{i=1}^{p}\sum_{j=1}^{p}(\alpha_i-\alpha_i^*)(\alpha_j-\alpha_j^*)\langle\textbf{x}_i,\textbf{x}_j\rangle+C\sum_{i=1}^{p}(\xi_i+\xi_i^*)+ \\ \color{blue}{-C\sum_{i=1}^{p}(\xi_i+\xi_i^*)+\sum_{i=1}^{p}\alpha_i\xi_i+\sum_{i=1}^{p}\alpha_i^*\xi_i^*}+ \\ -\color{green}{ \left(\varepsilon\sum_{j=1}^{p}\alpha_i+\sum_{j=1}^{p}\alpha_i\xi_i-\sum_{j=1}^{p}\alpha_i y_i+\sum_{j=1}^{p}\alpha_i \langle\textbf{x}_i,\textbf{x}_j\rangle+b\sum_{j=1}^{p}\alpha_i \right)}+\\ -\color{orange}{\left( \varepsilon\sum_{j=1}^{p}\alpha_i^*+\sum_{j=1}^{p}\alpha_i^*\xi_i^*+\sum_{j=1}^{p}\alpha_i^* y_i-\sum_{j=1}^{p}\alpha_i^* \langle\textbf{x}_i,\textbf{x}_j\rangle-b\sum_{j=1}^{p}\alpha_i^*\right)}$$

It is easy to notice that many terms will get cancelled due to opposite signs. Finally I get: $$\frac{1}{2}\sum_{i=1}^{p}\sum_{j=1}^{p}(\alpha_i-\alpha_i^*)(\alpha_j-\alpha_j^*)\langle\textbf{x}_i,\textbf{x}_j\rangle-\varepsilon\sum_{i=1}^{p}(\alpha_i+\alpha_i^*)+\sum_{i=1}^{p}y_i(\alpha_i-\alpha_i^*)+\sum_{i=1}^{p}(\alpha_i-\alpha_i^*)\langle\textbf{w},\textbf{x}_i\rangle+b\sum_{i=1}^{p}(\alpha_i^*-\alpha_i)$$

Based on the derivative of $L$ with respect to $b$ the last term vanishes, and introducing relation for $\textbf{w}$ from the derivatives of L one gets the final solution with the minus sign. $$\max_{\alpha, \alpha^*} \left[ \sum_{i=1}^{p}y_i(\alpha_i-\alpha_i^*)-\varepsilon\sum_{i=1}^{p}(\alpha_i+\alpha_i^*) -\frac{1}{2}\sum_{i=1}^{p}\sum_{j=1}^{p}(\alpha_i-\alpha_i^*)(\alpha_j-\alpha_j^*)\langle\textbf{x}_i,\textbf{x}_j\rangle \right]$$ subject to $\sum_{j=1}^{p}(\alpha_i-\alpha_i^*)=0$ and $\alpha_i,\alpha_i^* \in[0,C]$.

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.