 LFD Book Forum Support vectors in three dimensions
 Register FAQ Calendar Mark Forums Read

#1
 Yellin Member Join Date: Apr 2012 Posts: 26 Support vectors in three dimensions

10 events are randomly placed in a cube according to a probability density that is non-zero and finite everywhere in the cube. The events are classified into two classes in a linearly separable manner with at least one event in each class. What is the maximum possible number of support vectors needed with non-zero probability to maximize the margin?

a) 2
b) 3
c) 4
d) 5
e) none of the above
#2
 kkkkk Invited Guest Join Date: Mar 2012 Posts: 71 Re: Support vectors in three dimensions

I would think that the maximum no. of support vectors for any type of scenario (with 2 classes linearly separable) is N.
#3
 markland Member Join Date: Apr 2012 Posts: 30 Re: Support vectors in three dimensions

If I understand the question, it's asking what's the maximum number S such that there is a non-zero probability that S support vectors will be needed. I can see how N SVs might be needed, but the probability of that event would be 0.

BTW I don't know the answer. I'm guessing it's 4?
#4
 IamMrBB Invited Guest Join Date: Apr 2012 Posts: 107 Re: Support vectors in three dimensions

Good question. I, as always, dislike 'non of the above option'. maybe add 10 and/ or 9 as options. Think answer is c. 4.
#5
 Yellin Member Join Date: Apr 2012 Posts: 26 Re: Support vectors in three dimensions

ANSWER (read no further if you want to solve the problem yourself):

There must be at least one event on each of the parallel planes maximizing the margin. Given two fixed points, one on each of two parallel planes, the maximum distance between the planes while keeping them parallel is achieved by rotating them until the normals of the planes are parallel to the vector joining the two points. But that can be done without putting any events between the two planes if and only if there are exactly two support vectors. So two is the minimum number of support vectors. If, at the other extreme, there is no possible orientation change of the parallel planes without a support vector separating from one of them, there must be two more events on the planes, one for each degree of rotational freedom to be prevented. That gives the maximum number of support vectors, four. Any additional event on a plane could only be there with zero probability, because the volume within planes is zero fraction of the cube's volume.
#6
 mic00 Invited Guest Join Date: Apr 2012 Posts: 49 Re: Support vectors in three dimensions

Quote:
 Originally Posted by Yellin If, at the other extreme, there is no possible orientation change of the parallel planes without a support vector separating from one of them, there must be two more events on the planes, one for each degree of rotational freedom to be prevented. That gives the maximum number of support vectors, four.
I see it like this: for P>0 we should expect 30 degrees of freedom. If there are 4 SVs, then we have the following degrees of freedom: rotational orientation of the planes (2 degrees), distance between the planes (1 degree), offset from the origin (1 degree), and 2 degrees for each of the 4 SVs. That's 12 degrees for the SVs, plus 6*3 for the other points -- 30 total.

Quote:
 Originally Posted by Yellin Any additional event on a plane could only be there with zero probability, because the volume within planes is zero fraction of the cube's volume.
That's clear - restricting any other event to be an SV reduces its degrees of freedom by one.

Incidentally, now I'm a little bit curious about the number of SVs in general. I think I'd previously assumed that #SV < d+1 also had P=0, but that doesn't seem to be the case, and I wonder about problems that could be written around testing for that (the relationship between #SVs, number of dimensions, and size of training set)...
#7
 Yellin Member Join Date: Apr 2012 Posts: 26 Re: Support vectors in three dimensions

The degrees of freedom I was writing about are not the 3N ones of the N events. I was mentally adding support vectors until the parallel planes defining the margin are fixed by them. Perhaps I shouldn't have mentioned degrees of freedom at all, and just asked you to visualize how many support vectors there would have to be in order to freeze the planes defining the margin. But when I wrote about there being two degrees of freedom I meant the degrees of freedom of the orientation of the pair of parallel planes once they have been partly locked in position by one support vector on each. There are two coordinates needed to define the direction of the common normal of the pair of planes. To fix the orientation, continue adding support vectors. If a third support vector is added, there must be two on one plane. That plane will still not be fixed in orientation; it can rotate about an axis joining the two support vectors, and the parallel plane can be reoriented to keep it parallel, without separating any support vector from its plane. So only one degree of freedom of the normal is eliminated by having a second support vector on one plane. One more support vector is needed on either of the planes to completely fix the orientation of the two planes. So four support vectors is the maximum (with non-zero probability). There can be fewer than four support vectors, in which case the orientation of the two planes must have adjusted itself to maximize the margin given whatever number of support vectors there is.

The problem can be generalized to d dimensions and N events, and the answer is that the number of support vectors can be anything from 2 to min(d+1,N), depending on where the events are and how they're classified. Here's why:

Call " " the unit normal to the planes and call " " and " " two support vectors, one on one plane and one on the other. Then the remaining support vectors must be different from both and , and they must satisfy either or . To completely specify the d dimensional we need d equations, one of which is that is a unit vector. That leaves d-1 additional support vectors required, for a total of d+1. There can be more support vectors if they accidentally happen to land on one of the planes, but that has zero probability. There must be fewer if the number of points, N, is less than d+1. There can be fewer if the plane orientations are not completely fixed by the support vectors, but have adjusted themselves as best they can to maximize the margin.

The problem could have been made harder by asking about the more general case of d dimensions, but then it would have been more of a mathematical exercise than of thinking about what support vectors really are. And I hadn't thought of the above explanation at the time I wrote the problem.

Last edited by Yellin; 06-18-2012 at 06:40 AM. Reason: Add the generalization to d dimensions

 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 07:25 PM. The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.