Confusion related to convexity and concavity of a function - Computational Science Stack Exchange most recent 30 from scicomp.stackexchange.com 2019-06-27T10:17:05Z https://scicomp.stackexchange.com/feeds/question/5489 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://scicomp.stackexchange.com/q/5489 6 Confusion related to convexity and concavity of a function user34790 https://scicomp.stackexchange.com/users/3871 2013-03-09T15:54:47Z 2013-09-06T02:21:51Z <p>I was reading this paper <a href="http://www.ist.temple.edu/~vucetic/documents/wang11kdd.pdf" rel="nofollow noreferrer">http://www.ist.temple.edu/~vucetic/documents/wang11kdd.pdf</a> related to adaptive multi-hyperplane machine for non linear classification</p> <p>In that paper, they have mentioned about multiclass SVM, with multiple weights for each class.</p> <p>The loss for any classification is </p> <p>$l(x_n,y_n) = max_{i\epsilon y\\\y_n}(0,1 + max g(i,x_n) - g(y_n,x_n))$ </p> <p>where $y_n$ is the label for the nth example and $x_n$ is the features.</p> <p>I have this confusion when they do the training of this algorithm. They call this SVM MM(Multiple Hyperplane).</p> <p>They say the convex-approximated problem is defined as</p> <p>$min_{W}P(W|z) = \frac{\lambda}{2}||W||^2 + \frac{1}{N}\sum_{n=1}^{N}l_{cvx}(W;(x_n,y_n);z_n)$</p> <p>where they have the concave term $-g(y_n,z_n)$ replaced with the convex term $-w^T_{y_n,z_n}x_n$.</p> <p>I am not sure if I have described it clearly. But I am going to attach the screenshot of the paper as well. The thing is I didn't get what's the difference between $-g(y_n,z_n)$ and $-w^T_{y_n,z_n}x_n$. They seem the same term to me.</p> <p>I might be asking a lot. But can anyone provide some info?</p> <p><img src="https://i.stack.imgur.com/33iB6.png" alt="enter image description here"> <img src="https://i.stack.imgur.com/TNtk0.png" alt="enter image description here"></p> <p>I have marked by the red rectangle the part that I didn't understand. I might be asking a lot. But I didn't get that part. Why is it so?</p> https://scicomp.stackexchange.com/questions/5489/-/5497#5497 1 Answer by Geoff Oxberry for Confusion related to convexity and concavity of a function Geoff Oxberry https://scicomp.stackexchange.com/users/276 2013-03-10T00:57:06Z 2013-03-10T00:57:06Z <p><strong>Disclaimer:</strong> Most of my optimization-related work has been done in nonconvex optimization, and I have no training in Support Vector Machines (SVM) whatsoever.</p> <p>Based on what I can tell from reading Wikipedia and my optimization background, my guess is that they chose to replace the original nonconvex objective with an upper bound to formulate a convex restriction to the original problem. The "loss term" looks like a penalty term designed to ensure that the normal vectors of the hyperplanes in this particular SVM are all distinct; replacing the nonconvex term with a greater convex term in the objective function of a minimization problem only increases the penalty assigned to normal vectors that are "too similar".</p> <p>This modification was probably done to make the problem substantially easier to solve; convex optimization problems are solvable in polynomial time (as a function of the number of decision variables, constraints, and the number of bits it takes to store the inputs), whereas nonconvex optimization problems are not solvable in polynomial time, and typically have algorithms that are exponential run times (again, as a function of the number of decision variables, etc.). All of these exponential run time algorithms are sophisticated variants of guess-and-check, because that strategy is the best we can do in the absence of theoretical breakthroughs like $\mathcal{P} = \mathcal{NP}$.</p>