3
$\begingroup$

I want to determine the size of training data ($m$) when I know the parameters $VC(H)$, $δ$ and $e$. As I know the $VC$ bound satisfy this equation:

$$ \mathrm{error}_{\mathrm{true}}(h) \le \mathrm{error}_{\mathrm{train}}(h) + \sqrt\frac{VC(H) \times \ln\left(\frac{2m}{VC(H)} + 1\right) + \ln(4δ)}m $$

but how can I determine the size of training data ($m$) if I know the others?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Suppose you're aiming for a specific error rate. Suppose for the moment that there is no training error. You have an inequality involving all your known parameters and the unknown $m$, and you can solve it to obtain a value of $m$ that guarantees the specific true error rate, assuming that there is no training error. If you then run classification, you can correct for the training error and repeat.

The bound obtained through usage of VC dimension could be very pessimistic, and I don't know how useful it is in practice. Perhaps your instructor will address this later on in the course (or perhaps the issue will be swept under the rug).

Improve this answer
$\endgroup$
1
$\begingroup$

Thanks Yuval for your answer!:) I found the correct solution. The bound computed as follows:

$m \geq \frac{1}{e}(8\times VC(H)\times log_2(\frac{13}{e})+4\times log_2(\frac{2}{\delta}))$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.