|
I am going through the SVM lecture notes of Prof. Andrew Ng (CS 229). In page 6 he poses optimal margin classifier as a optimization problem. In the first formulation he says ||w|| = 1 is a nasty ``non-convex'' constraint. Can someone explain why this is a non-convex constraint? |
|
If you visualize the set of vectors w for which ||w|| = 1, you can see that it is not a convex set (refer to the definition of a convex set). For example, the vector (0,1) and the vector (0,-1) both satisfy the constraint, but any other convex combination of these two vectors does not satisfy the constraint; e.g., 0.5*(0,1) + 0.5*(0,-1) = (0,0) has a norm of 0 instead of 1. |
|
Geometrically, the vectors that satisfy ||w||=1 are located in the shell of a sphere, which is a non-convex set. In the other hand, if you have a constraint like ||w||<= 1, then the vectors are located in a ball, which is a convex set. |
|
A bit more on the formal definitions side. From Cover's "Elements of Information Theory" A function f(x) is said to be convex over (a,b) if for every x1 and x2 in the interval (a,b) in the function: f(lamx1+(1-lam)x2)<=lam*f(x1)+(1-lam)f(x2) Also, you can do the derivative test: If a function has a second derivative over an interval, the function is strictly convex. This way you can test any function for convexity in a nice way. |w| has no second derivative over any interval, since it is 0. Thus is is non convex in every point of it. @Leon I am talking about norm-2: ||w||^2 has a second derivative. While the norm-1 |w| does not have a second derivative.
(Jul 27 '11 at 10:12)
Anand
@Leon Anad is asking about the convexity of a set, not the convexity of a function. They are related, but they are not the same. Also note that ||w||_p is a convex function for all p>=1. What do you mean by "a function has a second derivative"? That the derivative exist, or that the derivative is non-zero?
(Jul 27 '11 at 10:41)
Alejandro
You are indeed right. The derivative test says that if the second derivative is > to zero at every point, then it it's strictly convex. Cover just has a different definition for exists. Another way to look at a convex set is to any set of point and join them by a line in the set, if you can take any pair of points and the line is part of the set, then it is convex. In this case, it is a shell, which means that if you take a point at the top and another at the bottom you have to get out of the set.
(Jul 27 '11 at 10:56)
Leon Palafox
A small warning: the second derivative test is a sufficient condition for strict convexity of a function. For instance, x^4 doesn't have a positive second derivative for all x in the domain, but it is still strictly convex.
(Jul 27 '11 at 11:11)
Alejandro
I think you are mixing strongly convex and strictly convex
(Jul 27 '11 at 11:18)
Leon Palafox
Why? This is a quote from section 3.6.4 (page 259 of the PDF) of Datorro's book (https://ccrma.stanford.edu/~dattorro/0976401304.pdf): "Strict inequality in (617) provides only a sufficient condition for strict convexity, but that is nothing new; videlicet, strictly convex real function f_i(x) = x^4 does not have positive second derivative at each and every x ∈ R . Quadratic forms constitute a notable exception where the strict-case converse holds reliably." Where equation (617) says that the second derivative is greater or equal than 0.
(Jul 27 '11 at 13:56)
Alejandro
showing 5 of 6
show all
|
