4
$\begingroup$

I'm building a non-kernelized Support Vector Machine classifier . The problem that I need to solve is:

$$\min_{w} \left(w^{t}w + \sum_{i=0}^{n}\max\left(0, 1-y_i\left(w^{t}x_{i} + b\right)\right)\right)$$

I want to solve this problem using subgradient descent, so I construct the cost function:

$$J_{1}(w,b) = w^{t}w + C\frac{1}{n}\sum_{i=0}^{n}\max(0, 1-y_i(w^{t}x_{i} + b))$$

But, I found one source online(I will provide a link if I manage to find it again) where they wrote the cost function as follows:

$$J_{2}(w,b) = \frac{1}{n}\sum_{i=0}^{n}(w^{t}w + C\max(0, 1-y_i(w^{t}x_{i} + b)))$$

I tried both versions of the cost function using their respective gradients, and it seems to me using $J_{2}$ gives a behavior of the SVM that looks most alike to the mental model of the behavior of SVM I have.

So my question is: which one of the two versions of the cost function is the correct one (or the better one) in this case, and why?

And more generally, should we write cost functions that are as whole written as an average over the training samples (as in $J_{2}$), or is it better to write some components as an average over the training samples and others not as an average (as in $J_{1}$)?

By the way, I'm using vanilla subgradient descent (as opposed to Stochastic GD), meaning my implementation makes updates of the weights and the bias using all the training samples per each update.

$\endgroup$
2
$\begingroup$

which one of the two versions of the cost function is the correct one (or the better one) in this case, and why?

I suspect you were intending to take the average, in which case the sum would typically be written from $i=1$ to $n$. If that's the case, then your expressions $J_1$ and $J_2$ for the cost function would be equivalent (you can rearrange each to get the other).

And more generally, should we write cost functions that are as whole written as an average over the training samples (as in $J_2$), or is it better to write some components as an average over the training samples and others not as an average (as in $J_1$)?

In my experience, the form of $J_1$ is more typical. It clearly expresses the cost function as a sum of two terms: 1) the loss (hinge loss in this case), which is summed/averaged over data points, and 2) the penalty/regularization term ($\ell_2$ penalty in this case), which depends only on the weights/parameters.

Not all cost functions can be written as a sum/average over data points. For example, some might involve pairs of data points. Or, an operation other than a sum might be of interest. Or, considering cost functions for general optimization problems, there may be no data at all.

Edit: Proof that $J_1$ and $J_2$ are equivalent

I'll assume here that the sums should be from $1$ to $n$.

Start with the expression for $J_2$:

$$\frac{1}{n} \sum_{i=1}^n \left ( w^T w + C \max(0, 1-y_i(w^T x_i + b)) \right )$$

Split the sum into two separate sums:

$$= \frac{1}{n} \sum_{i=1}^n w^T w + \frac{1}{n} \sum_{i=1}^n C \max(0, 1-y_i(w^T x_i + b))$$

Factor out terms that don't depend on $i$:

$$= \frac{1}{n} w^T w \sum_{i=1}^n 1 + C \frac{1}{n} \sum_{i=1}^n \max(0, 1-y_i(w^T x_i + b))$$

Note that $\sum_{i=1}^n 1 = n$:

$$= w^T w + C \frac{1}{n} \sum_{i=1}^n \max(0, 1-y_i(w^T x_i + b))$$

This is now the expression for $J_1$.

$\endgroup$
  • $\begingroup$ Can you please show how you can rearrange $J_{1}$ to get $J_{2}$, because I don't think they are equivalent? In $J_{2}$ you add more importance to the norm of the weights because you add the dot product n-times instead of once. $\endgroup$ – user3071028 Jul 29 '18 at 10:36
  • $\begingroup$ I edited the post to show what you're asking for $\endgroup$ – user20160 Jul 29 '18 at 12:58
1
$\begingroup$

If we excluded the $w^Tw$ term, the two objectives would be equivalent as they would be multiples of each other. So the only difference is weither this term is weighted or not. The $w^Tw$ term serves to penalize large weights to prevent overfitting. Generally regularization terms get their own weighting parameter, often denoted as $\lambda$ that toggles the relative importance of the two terms: $$\lambda w^Tw + \frac{1}{n}\sum^n_{i=1} f(x_i,y_i)$$ Since the regularization term doesn't depend on the number of training examples, there no intuitive reason for its weight to be $1/n$ but it might still be useful to use $\lambda <1$. Often the optimal value for this parameter is found via cross validation with left out/unseen data.

$\endgroup$

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.