Timeline for Given a set of points in two dimensional space, how can one design decision function for SVM?
Current License: CC BY-SA 3.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2014 at 3:10 | comment | added | TenaliRaman | @whuber Please check my edit to the addendum and see if that is more reasonable now. | |
| Apr 17, 2014 at 3:10 | history | edited | TenaliRaman | CC BY-SA 3.0 |
added 166 characters in body
|
| Apr 16, 2014 at 19:40 | comment | added | TenaliRaman | @whuber Absolutely! I know what you are trying to do :-) I am trying to understand whether you got the point I was trying to make. In case, my earlier comment made sense, I will modify the addendum appropriately. | |
| Apr 16, 2014 at 19:00 | comment | added | whuber♦ | It is hard for me--and likely for many others--to understand what you write when it includes statements that are clearly not true. It makes one wonder what you really mean, whether you have typos, whether you are mistaken, or whether we, the readers, actually understand. It causes readers to respond with statements like "It seems like SVMs become harder to understand every time I try to figure them out." As a moderator I am trying to nudge you to clean up your answer so that it more clearly expresses the ideas you want to get across and causes less confusion for its readers. | |
| Apr 16, 2014 at 18:33 | comment | added | TenaliRaman | Wait, why are we doing this again? It is our desire that FMs be greater than equal to 1. That is when we solve our optimization, all points must have satisfied FMs >= 1. Maybe you are having problems because I have used FMs = 1 everywhere in the derivation? Would you be comfortable if I replaced them with FMs >= 1 ? We will simply derive that GMs >= 2 / |w|_2, so essentially, it will be like maximizing the lower bound. | |
| Apr 16, 2014 at 18:05 | comment | added | whuber♦ | I used $(w_0,w_1,w_2)=(-\epsilon/2,0,2/\epsilon)$. | |
| Apr 16, 2014 at 17:54 | comment | added | TenaliRaman | @whuber Ah sorry, I see what you are saying. What is the weight vector that you are using to compute the FMs? | |
| Apr 16, 2014 at 17:42 | comment | added | whuber♦ | The second looks ok: I hadn't noticed the $0$s of the first program had been replaced by $1$s. Thanks for making the change. Now that it makes sense, I have scanned down to your addendum. I don't see why the functional margin of shortest-distance points must be $1$. A counterexample is $\{(-9,0,-1),(9,0,-1),(0,-3,-1),(4,-1,-1);(-9,3,1),(9,3,1),(4,1,1),(0,\epsilon \gt 0,1)\}$. The shortest-distance points are $(4,-1,1),(4,1,1)$ whose distance is $2$ but their FMs will be $2(1-\epsilon)/\epsilon$ and $2(1+\epsilon)/\epsilon,$ both of which are huge when $\epsilon$ is small. | |
| Apr 16, 2014 at 17:04 | comment | added | TenaliRaman | @whuber I agree with the first having a problem, I have modified it slightly now to escape that issue. However, the second is the hard margin SVM formulation. I would like to understand what exactly is your issue with that? | |
| Apr 16, 2014 at 17:03 | history | edited | TenaliRaman | CC BY-SA 3.0 |
added 6 characters in body
|
| Apr 16, 2014 at 16:11 | comment | added | whuber♦ | The linear program you posit to "define a classifier" has a huge problem. The minimum might never be attained: if there exists any solution with $w_0+w_1+w_2\lt 0$, then all positive multiples of that solution work (as well as many more) and the minimum approaches $-\infty$, which is useless; otherwise, the minimum is attained as $w_0+w_1+w_2$ approaches $0$ from above, which is also useless. Your second program has equally fatal flaws. | |
| Apr 4, 2013 at 16:14 | comment | added | TenaliRaman | @entropy : You are asking the right questions, don't worry you will reach enlightenment :-) | |
| Apr 3, 2013 at 10:34 | comment | added | entropy | It seems like SVMs become harder to understand every time I try to figure them out. | |
| Apr 3, 2013 at 10:19 | comment | added | TenaliRaman | @entropy Having said the above, you might have realized by now that if you properly rotate and shift the points, even a line passing through the origin should be able to separate the classes. However, usually finding this right rotation and shift is not easy, compared to just learning the bias term. | |
| Apr 3, 2013 at 10:18 | comment | added | TenaliRaman | @entropy $w^{T}x$ is a hyperplane passing through origin. To cover the space of all linear equations you need the bias term. Think of points residing in 2D and let us say that you are trying to find a line that separates these points. However these points all lie in the first quadrant. Now one can arrange these points such that they are separable but not by any line that passes through the origin. However, a line with a proper bias can do it. | |
| Apr 3, 2013 at 9:08 | comment | added | entropy | can someone please explain to me why we are including a bias term b or $w_0$. Why not just exclude it? | |
| Jan 3, 2013 at 0:15 | comment | added | TenaliRaman | @entropy I have updated the answer with the geometric margin explanation. | |
| Jan 3, 2013 at 0:13 | history | edited | TenaliRaman | CC BY-SA 3.0 |
added 1237 characters in body
|
| Jan 2, 2013 at 23:47 | comment | added | TenaliRaman | @entropy thanks I have fixed the typo. I will add the geometric margin explanation. | |
| Jan 2, 2013 at 23:31 | history | edited | TenaliRaman | CC BY-SA 3.0 |
added 4 characters in body
|
| Jan 2, 2013 at 23:09 | comment | added | entropy | Can you show that geometric margin corresponding to this requirement comes out to be $\frac{1}{||w||}$, please? | |
| Jan 2, 2013 at 23:07 | comment | added | entropy | isn't there a typo in that $w_0 + w_1x^i_1 + w_2x^i_2 < 1$ should be $w_0 + w_1x^i_1 + w_2x^i_2 \leq -1$? | |
| Nov 29, 2012 at 12:30 | comment | added | TenaliRaman | @naresh I have added my cvx script also to the answer above. As one can see from the script, going from here to a general SVM is not very hard. In fact, writing code for SVM is very very easy and given that one has access to some nifty libraries like MOSEK, CVX etc. only makes things simpler (making it faster on the other hand is a harder problem). The only one thing I haven't discussed in my answer above is consideration of slack variables. But it is a very common thing to all optimization problems. Understanding those shouldn't be that difficult. | |
| Nov 29, 2012 at 12:25 | history | edited | TenaliRaman | CC BY-SA 3.0 |
added 329 characters in body
|
| Nov 29, 2012 at 11:58 | vote | accept | naresh | ||
| Nov 29, 2012 at 9:55 | comment | added | TenaliRaman | @naresh Yeap, solving this is in cvx gave me the exact same solution that you have $w = [0, -2, 3]$. | |
| Nov 29, 2012 at 7:58 | comment | added | naresh | updated with solution.. Can you please see if i got it right? | |
| Nov 17, 2012 at 8:43 | comment | added | TenaliRaman | @naresh This might be a good exercise. You should try writing out optimization problem for the example you gave. | |
| Nov 17, 2012 at 6:08 | comment | added | naresh | Thanks for the explanation. Can you also kindly show how to apply all this to the example i have mentioned in the question? | |
| Nov 17, 2012 at 5:33 | history | answered | TenaliRaman | CC BY-SA 3.0 |