# If the training data are linearly separable, which of the following $L(w)$ has less optimum answer for $w$, when $y = w^Tx$?

I'm studying machine learning and I came into a challenging question.

The answer is 2. But based on my ML notes, all of them are true. Where are the wrong points?

• Can you please tell us in which context does this question/problem pop up? Is this a homework question? Can you provide the link to the exam/homework/challenge? This seems to be related to support vector machines, but I suggest that you edit your post to provide more context. Moreover, what do your notes actually tell? Do you understand the question? Because I'm not fully sure I really understand this question or, specificallt, what they mean by "less optimum answer". – nbro Jan 8 at 11:30
• @nbro the question is about less optimal hyperplanes. if we know the w vector and bias term, we can draw the discriminant hyperplane. As pointed in the question, the training data are linearly separable. So we may have a lot of discriminant hyperplane. In 2 there is a regularization term, what is its role? It makes the loss function to find less optimal w vectors? – Emiliiii Jan 8 at 11:49
• This really seems to be related to SVMs. Please, provide a link to the resource where you're reading this to have more context. So, as far as I recall, equation 2 is an equation that allows for some tolerance and that some points may not be correctly classified. Check the soft-margin here: en.wikipedia.org/wiki/Support-vector_machine for a similar formula. – nbro Jan 8 at 11:51
• Would you clarify a bit more? what will happen when C goes to infinity? – Emiliiii Jan 8 at 12:03
• Welcome to AI.SE. Just a hint. Try to figure out what exactly are we optimising here vs what we want to optimize. Although the correct answer is not very mathematically rigorous but it kind of makes sense. – DuttaA Jan 8 at 12:10

## 2 Answers

Since the data is linearly separable linear model $$y = w^Tx$$ will be able to perfectly classify all the examples. That means that loss functions $$L_1(w), L_3(w)$$ and $$L_4(w)$$ will have a value of 0 (since all examples are correctly classified). For the loss $$L_2(w)$$ second term will be 0 if all examples are correctly classified. The first term of $$L_2(w)$$ $$$$\frac{1}{2}||w||^2_2$$$$ will be not be minimized to 0 (unless optimal $$w = \mathbf{0}$$) so $$L_2(w) > 0$$. Optimizer will try to minimize $$L_2(w)$$ to be 0, so because of the penalty to $$w$$ it will try to find the best tradeoff between minimizing $$w$$ and loss due to misclassification so the resulting $$w$$ may not be the best to achieve optimal classification.

First things first. What is an optimal $$w$$?. In this case it is supposed to be not only the one that minimizes the emprical /sample loss, but also non-trivial as we shall sonn see. Now inspect the loss functions, we see a term $$-y_iw^Tx_i$$ coming up. What exactly is this term? It can be anything. The correct term would have been $$-y_i(w^Tx_i + b)$$, or atleast I will assume this term, but the reasoning will exactly be the same without this term.

Now this term is well defined and since the Eucledian distance of a point, along with sign, $$x_i$$ from the hyperplane $$w^Tx + b=0$$ (the proof for this can be found easily), is given by $$w^Tx_i + b$$. So if the datapoint is supposed to have $$y_i=-1$$ but according to the classifier it gives $$w^Tx_i + b = l_i > 0$$, then one cane see $$-y_il_i > 0$$, hence $$\max (0, -y_i l_i) = -y_i l_i$$ a positive loss, and the same will apply to case when $$y_i = 1$$ and $$w^Tx_i + b = l_i <0$$

We see another assumption, the datapoints are linearly seperable. This means, there exists a classifier (or a hyperplane) which can completely seperate the 2 classes. Now if one inspects the loss function $$1,3,4$$ all of them have one goal to make $$\max (0, -y_i l_i) = 0, \forall i$$. A point to note is that $$1$$ does this by directly reducing $$\sum_{i=1}^n \max (0, -y_i l_i)$$, $$3$$ does this using the $$0-1$$ loss i.e if the instance is wrongly classified (or $$-y_il_i > 0$$), then incur $$\frac{1}{n}$$ loss else $$0$$, while $$4$$ incurs a loss of $$\frac{1}{n}(w^Tx_i + b)^2$$ for each wrong classification. It is very important to note that the solution of all these 3 problems are all the same $$w^*,b^*$$ which classifies the dataset correctly, which makes the problem equivalent. (This may not hold under some very similar looking loss functions, so it is a point to take care about, a problem is equivalent only if it results in the same solution).

In $$2$$, first $$C \rightarrow \infty$$ is an incorrect statement, since then not only does it become mathematically unsound (atleast for me), it also means $$2$$ is the same as $$1,3,4$$. Why? $$C$$ is a weighting factor, it decides how much priority the algorithm minimizing loss will give to the term $$C \sum_{i=1}^n \max(0,-y_il_i)$$. If say $$C=0$$ then you are basically optimizing $$||w||_2^2$$ whose optimal value is at $$w=0$$. hence, we get nothing useful as optimizing $$||w||_2^2$$ has no connection with our objective of reducing misclassifications. But if, $$0.5||w||_2^2 + C \sum_{i=1}^n \max(0,-y_il_i)$$ is used the algorithm is now giving some weightage to minimizing both the $$||w||_2^2$$ as well as the misclassifications. If $$C$$ is very small the algorithm will prefer to minimize $$||w||_2^2$$ rather than $$C \sum_{i=1}^n \max(0,-y_il_i)$$. Thus giving a solution which may not be optimal, as per the dataset. But, if $$C$$ is very large the algorithm will mostly try to minimize $$C \sum_{i=1}^n \max(0,-y_il_i)$$, but still it will give some weightage in minimizng $$||w||_2^2$$, hence may not find an optimal hyperplane. If $$C \rightarrow \infty$$ it is matheatically ill defined (as per my knowledge) so I won't go into it.

But, all these aforementioned explanation (i.e the tradeoff between optimizaing two different objectives) will be useful only when there are some additional constraints, like instead of $$\max(0,-y_il_i)$$ it is $$\max(0,1-y_il_i)$$ where making $$w$$ bigger actually makes sense as it will also increase $$l_i$$ (i.e the same hyperplane denoted by a larger $$w$$ say $$kw$$ will make l_i large hence $$-l_iy_i$$ small if correctly classified, but this doesn't make sense if we are talking about the same hyperplane), hence the $$||w||_2^2$$ term opposes such an increase. This is a very famous formulation of loss used in SVM.

But, the challenging part in this question is the assumption 'linearly seperable' and also the additional constraint is missing (which is present in SVMs). So if $$w^*,b^*$$ incurs $$0$$ classification error so will $$kw^*, b^*$$ where $$k$$ is any scaling factor. And since $$C$$ is very large the second term in $$2$$ must be $$0$$. Thus, any $$kw^*, b^*$$ will work to make the second term 0. But, the first term now becomes $$0.5k^{2}||w^*||_2^2$$, where $$w^*$$ denotes the optimal hyperplane, and hence fixed. Thus the first term will choose $$|k| \rightarrow 0$$ or basically $$k=0$$ to minmize the 1st term and the second term now simply becomes $$C\sum_{i=1}^n \max(0,-y_ib)$$ which can be made $$0$$ by choosing $$b=0$$. Thus, a $$0$$ loss when $$kw^*=0,b^*=0$$ or a trivial solution and definitely not optimal as this will be true for all linearly seperable datasets.

I assumed and extra $$b$$ term to leverage linear seperability, without it the reasoning becomes easier and you can follow the exact same line of reasoning, albeit the problem might not be linearly seperable anymore. The solution may seem not very elegant but this is a standard line of reasoning in optimization problems where the optimization variable is changed from $$w \rightarrow k$$, where $$w \in \mathbb{R^n}$$ and $$k \in \mathbb{R}$$.

In short for $$2$$ the solution produced will be $$w^*=0,b^*=0$$ which will be the best solution but easily seen as trivial and non optimal at all.