<p>In Vapnik's book "Statistical Learning Theory", Theorem 10.5 states that - for a Support Vector Machine - the expected probability of error (of the optimal hyperplane) is upper bounded by $1/(l+1)$ times the expected number of support vectors.</p>

<p>Is the expected probability of error - the LHS of inequality 10.32 - non-increasing in the number $l$ of training samples?</p>

CC BY-SA 3.0
2014-01-20T14:39:38.573Z
I do not see why your first paragraph does not answer your question. Can you make the question stand on its own, so that it can be understood without referring to the book?
Sasho Nikolov
CC BY-SA 3.0
2014-01-20T16:35:38.950Z
Sasho, sorry but I do not understand what do you mean with your first comment. Do you mean that the claim is true?
user693
CC BY-SA 3.0
2014-01-20T17:14:01.663Z
Disregard the first comment, I misunderstood. Still, could you reword the question so that it can be understood without looking up an equation in the book?
Sasho Nikolov
CC BY-SA 3.0
2014-01-20T20:39:17.743Z
I think it is hard to meet your question because I should define the expectation of the probability of error, the leave-one-out procedure and the notion of support vectors. In other words, I would need to insert the entire chapter on Support Vector Machines.
user693
CC BY-SA 3.0
2014-01-20T20:42:26.233Z
However, I can at least refer you to Section 2.3 in [http://olivier.chapelle.cc/pub/span_lmc.pdf] for the Leave-One-Out procedure.
user693
CC BY-SA 3.0
2014-02-07T22:32:51.610Z
Why does my answer to http://cstheory.stackexchange.com/questions/5314/support-vector-machines not answer your question?
Lev Reyzin
CC BY-SA 3.0
2014-02-07T22:39:35.087Z
I am sorry, I do not understand your question. Can you please explain? Thanks a lot!
user693
CC BY-SA 3.0
2014-02-07T23:42:23.660Z
When I first read the title, I thought it was some kind of joke about the number of errors in the book !
Suresh Venkat
CC BY-SA 3.0
2014-02-08T00:17:32.983Z
you dont give the formula but generally, empirically & possibly in some proofs/formally, error tends to decrease for increasing training samples for all nearly all ML/function approximating technologies, but decreases asymptotically. right?
vzn
CC BY-SA 3.0
2014-02-08T07:45:26.213Z
@vzn: In which formulas the expected probability of error is non-increasing? All the formulas I know regard non-increasing upper bounds on the expected probability of error, that do not mean that the true expected probability of error is a non-increasing function. I am not interested in the practice, I am asking a theoretical question.
user693
CC BY-SA 3.0
2014-02-08T15:30:12.597Z
?? still not following. are you talking about training error (error in fitting the training samples) or prediction error (error in predicting unseen samples)?
vzn
CC BY-SA 3.0
2014-02-08T18:23:23.513Z
I am talking about the expected probability of error, which is your "error in predicting unseen samples", or the so called generalization error. Let's even suppose that the training error is zero.
user693
<machine-learning><lg.learning><st.statistics><vc-dimension>
Expected probability of error in Vapnik's book
user693
# Expected probability of error in Vapnik's book

(Asked by: username_0 on 2014-01-19)

In Vapnik's book "Statistical Learning Theory", Theorem 10.5 states that - for a Support Vector Machine - the expected probability of error (of the optimal hyperplane) is upper bounded by $1/(l+1)$ times the expected number of support vectors.

Is the expected probability of error - the LHS of inequality 10.32 - non-increasing in the number $l$ of training samples?

**Tags:** machine-learning, lg.learning, st.statistics, vc-dimension
> **Comments:**
> **username_1**: I do not see why your first paragraph does not answer your question. Can you make the question stand on its own, so that it can be understood without referring to the book?  
> **username_0**: Sasho, sorry but I do not understand what do you mean with your first comment. Do you mean that the claim is true?  
> **username_1**: Disregard the first comment, I misunderstood. Still, could you reword the question so that it can be understood without looking up an equation in the book?  
> **username_0**: I think it is hard to meet your question because I should define the expectation of the probability of error, the leave-one-out procedure and the notion of support vectors. In other words, I would need to insert the entire chapter on Support Vector Machines.  
> **username_0**: However, I can at least refer you to Section 2.3 in [http://olivier.chapelle.cc/pub/span_lmc.pdf] for the Leave-One-Out procedure.  
> **username_2**: Why does my answer to http://cstheory.stackexchange.com/questions/5314/support-vector-machines not answer your question?  
> **username_0**: I am sorry, I do not understand your question. Can you please explain? Thanks a lot!  
> **username_3**: When I first read the title, I thought it was some kind of joke about the number of errors in the book !  
> **username_4**: you dont give the formula but generally, empirically & possibly in some proofs/formally, error tends to decrease for increasing training samples for all nearly all ML/function approximating technologies, but decreases asymptotically. right?  
> **username_0**: @vzn: In which formulas the expected probability of error is non-increasing? All the formulas I know regard non-increasing upper bounds on the expected probability of error, that do not mean that the true expected probability of error is a non-increasing function. I am not interested in the practice, I am asking a theoretical question.  
> **username_4**: ?? still not following. are you talking about training error (error in fitting the training samples) or prediction error (error in predicting unseen samples)?  
> **username_0**: I am talking about the expected probability of error, which is your "error in predicting unseen samples", or the so called generalization error. Let's even suppose that the training error is zero.  

---

## 0 answers

