Skip to main content
added 191 characters in body
Source Link
Marc Claesen
  • 18.7k
  • 2
  • 55
  • 76

The cost function of SVM is: $$\min_{\alpha,\xi,b} \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^n \xi_i$$

where $\xi$ are the slack variables (0 for hard margin) and $$ ||\mathbf{w}||^2 =\mathbf{w}^T\mathbf{w} = \sum_{i\in \mathcal{S}}\sum_{j\in \mathcal{S}} \alpha_i \alpha_j y_i y_j \kappa(\mathbf{x}_i,\mathbf{x}_j) $$

A couple of important properties can be derived from the Langrangian (here with slack variables):

$$L_p = \frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^n\xi_i -\sum_{i=1}^n\alpha_i\Big[y_i\big(<\mathbf{w},\varphi(\mathbf{x}_i)>+b\big)-(1-\xi_i)\Big]-\sum_{i=1}^n\mu_i\xi_i. $$

By setting the partial derivative to $\xi$ (the slack variables) to zero, we obtain the following equation in $\alpha$: $$\frac{\partial L_p}{\partial \xi_i}=0 \quad \rightarrow \quad \alpha_i=C-\mu_i, \quad \forall i$$ In the presence of slack variables, all support values ($\alpha$'s) are bound by $0$ and $C$. They are not all equal. 

In the absence of slack variables (hard margin SVM), $\alpha$ values are not equal because $\alpha$ is a direct part of the objective function as shown in the first two equations. In hard margin SVM, the cost function is a weighted quadratic function in $\alpha$ where the kernel evaluations between corresponding points determine the weights. Since not all weights are equal, the $\alpha$ values aren't either.

This is more apparant in least-squares SVM (LS-SVM), where all training points become support vectors due to the problem formulation. One of the original methods proposed to obtain sparsity in LS-SVM involved pruning support vectors with small $\alpha$ values.

The cost function of SVM is: $$\min_{\alpha,\xi,b} \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^n \xi_i$$

where $\xi$ are the slack variables (0 for hard margin) and $$ ||\mathbf{w}||^2 =\mathbf{w}^T\mathbf{w} = \sum_{i\in \mathcal{S}}\sum_{j\in \mathcal{S}} \alpha_i \alpha_j y_i y_j \kappa(\mathbf{x}_i,\mathbf{x}_j) $$

A couple of important properties can be derived from the Langrangian (here with slack variables):

$$L_p = \frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^n\xi_i -\sum_{i=1}^n\alpha_i\Big[y_i\big(<\mathbf{w},\varphi(\mathbf{x}_i)>+b\big)-(1-\xi_i)\Big]-\sum_{i=1}^n\mu_i\xi_i. $$

By setting the partial derivative to $\xi$ (the slack variables) to zero, we obtain the following equation in $\alpha$: $$\frac{\partial L_p}{\partial \xi_i}=0 \quad \rightarrow \quad \alpha_i=C-\mu_i, \quad \forall i$$ In the presence of slack variables, all support values ($\alpha$'s) are bound by $0$ and $C$. They are not all equal. In the absence of slack variables, $\alpha$ values are not equal because $\alpha$ is part of the objective function.

This is more apparant in least-squares SVM (LS-SVM), where all training points become support vectors due to the problem formulation. One of the original methods proposed to obtain sparsity in LS-SVM involved pruning support vectors with small $\alpha$ values.

The cost function of SVM is: $$\min_{\alpha,\xi,b} \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^n \xi_i$$

where $\xi$ are the slack variables (0 for hard margin) and $$ ||\mathbf{w}||^2 =\mathbf{w}^T\mathbf{w} = \sum_{i\in \mathcal{S}}\sum_{j\in \mathcal{S}} \alpha_i \alpha_j y_i y_j \kappa(\mathbf{x}_i,\mathbf{x}_j) $$

A couple of important properties can be derived from the Langrangian (here with slack variables):

$$L_p = \frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^n\xi_i -\sum_{i=1}^n\alpha_i\Big[y_i\big(<\mathbf{w},\varphi(\mathbf{x}_i)>+b\big)-(1-\xi_i)\Big]-\sum_{i=1}^n\mu_i\xi_i. $$

By setting the partial derivative to $\xi$ (the slack variables) to zero, we obtain the following equation in $\alpha$: $$\frac{\partial L_p}{\partial \xi_i}=0 \quad \rightarrow \quad \alpha_i=C-\mu_i, \quad \forall i$$ In the presence of slack variables, all support values ($\alpha$'s) are bound by $0$ and $C$. They are not all equal. 

In the absence of slack variables (hard margin SVM), $\alpha$ values are not equal because $\alpha$ is a direct part of the objective function as shown in the first two equations. In hard margin SVM, the cost function is a weighted quadratic function in $\alpha$ where the kernel evaluations between corresponding points determine the weights. Since not all weights are equal, the $\alpha$ values aren't either.

This is more apparant in least-squares SVM (LS-SVM), where all training points become support vectors due to the problem formulation. One of the original methods proposed to obtain sparsity in LS-SVM involved pruning support vectors with small $\alpha$ values.

Source Link
Marc Claesen
  • 18.7k
  • 2
  • 55
  • 76

The cost function of SVM is: $$\min_{\alpha,\xi,b} \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^n \xi_i$$

where $\xi$ are the slack variables (0 for hard margin) and $$ ||\mathbf{w}||^2 =\mathbf{w}^T\mathbf{w} = \sum_{i\in \mathcal{S}}\sum_{j\in \mathcal{S}} \alpha_i \alpha_j y_i y_j \kappa(\mathbf{x}_i,\mathbf{x}_j) $$

A couple of important properties can be derived from the Langrangian (here with slack variables):

$$L_p = \frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^n\xi_i -\sum_{i=1}^n\alpha_i\Big[y_i\big(<\mathbf{w},\varphi(\mathbf{x}_i)>+b\big)-(1-\xi_i)\Big]-\sum_{i=1}^n\mu_i\xi_i. $$

By setting the partial derivative to $\xi$ (the slack variables) to zero, we obtain the following equation in $\alpha$: $$\frac{\partial L_p}{\partial \xi_i}=0 \quad \rightarrow \quad \alpha_i=C-\mu_i, \quad \forall i$$ In the presence of slack variables, all support values ($\alpha$'s) are bound by $0$ and $C$. They are not all equal. In the absence of slack variables, $\alpha$ values are not equal because $\alpha$ is part of the objective function.

This is more apparant in least-squares SVM (LS-SVM), where all training points become support vectors due to the problem formulation. One of the original methods proposed to obtain sparsity in LS-SVM involved pruning support vectors with small $\alpha$ values.