LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Create New Homework Problems

Reply
 
Thread Tools Display Modes
  #1  
Old 06-13-2012, 06:18 PM
Yellin Yellin is offline
Member
 
Join Date: Apr 2012
Posts: 26
Default 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
Reply With Quote
  #2  
Old 06-13-2012, 06:50 PM
kkkkk kkkkk is offline
Invited Guest
 
Join Date: Mar 2012
Posts: 71
Default 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.
Reply With Quote
  #3  
Old 06-13-2012, 09:05 PM
markland markland is offline
Member
 
Join Date: Apr 2012
Posts: 30
Default 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?
Reply With Quote
  #4  
Old 06-13-2012, 11:30 PM
IamMrBB IamMrBB is offline
Invited Guest
 
Join Date: Apr 2012
Posts: 107
Default 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.
Reply With Quote
  #5  
Old 06-16-2012, 12:12 PM
Yellin Yellin is offline
Member
 
Join Date: Apr 2012
Posts: 26
Default 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.
Reply With Quote
  #6  
Old 06-16-2012, 03:19 PM
mic00 mic00 is offline
Invited Guest
 
Join Date: Apr 2012
Posts: 49
Default Re: Support vectors in three dimensions

I like this problem, though I'm a little confused about this part of the proof:

Quote:
Originally Posted by Yellin View Post
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 View Post
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)...
Reply With Quote
Reply

Thread Tools
Display Modes

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 Jump


All times are GMT -7. The time now is 03:24 AM.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
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.