Why is a lower bound necessary in proofs of VC-dimensions for various examples of hypotheses?Performance and architecture of neural network for increased dimensionsWhy CNN doesn't give higher accuracy over simple MLP network? [From Keras examples]Multilabel image classification: is it necessary to have traning data for each combination of labels?Why is it necessary to clean/preprocess data if the unseen real data is bound to consist missing values, outliers etc.?Correct learning algorithm for grouped examplesHow to choose negative examples for recommendation system?Why derivatives are accumulated over all examples in back propagation?CNN: Should I include null examples in the training set for image segmentationis it necessary for Artificial NN to be fully connected or only fully connected NN is called ANN?
Selecting a secure PIN for building access
Is there a legal ground for stripping the UK of its UN Veto if Scotland and/or N.Ireland split from the UK?
Besides the up and down quark, what other quarks are present in daily matter around us?
Identifying my late father's D&D stuff found in the attic
What word means "to make something obsolete"?
Is it cheaper to drop cargo than to land it?
In Avengers 1, why does Thanos need Loki?
Airbnb - host wants to reduce rooms, can we get refund?
Why wasn't the Night King naked in S08E03?
Upside-Down Pyramid Addition...REVERSED!
What happens to the Time Stone?
How can I close a gap between my fence and my neighbor's that's on his side of the property line?
How to reply this mail from potential PhD professor?
Python password manager
I need a disease
Does this article imply that Turing-Computability is not the same as "effectively computable"?
My ID is expired, can I fly to the Bahamas with my passport?
How to get a product new from and to date in phtml file in magento 2
How long would it take for people to notice a mass disappearance?
Has a commercial or military jet bi-plane ever been manufactured?
How do I tell my manager that his code review comment is wrong?
Is there formal test of non-linearity in linear regression?
Would a 1/1 token with persist dying trigger on death effects a second time?
Can the 歳 counter be used for architecture, furniture etc to tell its age?
Why is a lower bound necessary in proofs of VC-dimensions for various examples of hypotheses?
Performance and architecture of neural network for increased dimensionsWhy CNN doesn't give higher accuracy over simple MLP network? [From Keras examples]Multilabel image classification: is it necessary to have traning data for each combination of labels?Why is it necessary to clean/preprocess data if the unseen real data is bound to consist missing values, outliers etc.?Correct learning algorithm for grouped examplesHow to choose negative examples for recommendation system?Why derivatives are accumulated over all examples in back propagation?CNN: Should I include null examples in the training set for image segmentationis it necessary for Artificial NN to be fully connected or only fully connected NN is called ANN?
$begingroup$
In the book "Foundations of Machine Learning" there are examples of proving the VC dimensions for various hypotheses, e.g., for axis-aligned rectangles, convex polygons, sine functions, hyperplanes, etc.
All proofs first derive a lower bound, and then show an upper bound. However, why not just derive the upper bound since the definition of VC dimension only cares about the "largest" set that can be shattered by hypothesis set $mathcalH$? Since all examples ends up with a lower bound matching the upper bound, is the lower bound just helpful/useful to set a target when trying to show an upper bound?
Reference:
From page 41 of this book pdf version
https://pdfs.semanticscholar.org/e923/9469aba4bccf3e36d1c27894721e8dbefc44.pdf
machine-learning pac-learning vc-theory
asked Apr 10 at 0:44
ML studentML student
594
$endgroup$
add a comment |
$begingroup$
In the book "Foundations of Machine Learning" there are examples of proving the VC dimensions for various hypotheses, e.g., for axis-aligned rectangles, convex polygons, sine functions, hyperplanes, etc.
All proofs first derive a lower bound, and then show an upper bound. However, why not just derive the upper bound since the definition of VC dimension only cares about the "largest" set that can be shattered by hypothesis set $mathcalH$? Since all examples ends up with a lower bound matching the upper bound, is the lower bound just helpful/useful to set a target when trying to show an upper bound?
Reference:
From page 41 of this book pdf version
https://pdfs.semanticscholar.org/e923/9469aba4bccf3e36d1c27894721e8dbefc44.pdf
machine-learning pac-learning vc-theory
asked Apr 10 at 0:44
ML studentML student
594
$endgroup$
add a comment |
$begingroup$
In the book "Foundations of Machine Learning" there are examples of proving the VC dimensions for various hypotheses, e.g., for axis-aligned rectangles, convex polygons, sine functions, hyperplanes, etc.
All proofs first derive a lower bound, and then show an upper bound. However, why not just derive the upper bound since the definition of VC dimension only cares about the "largest" set that can be shattered by hypothesis set $mathcalH$? Since all examples ends up with a lower bound matching the upper bound, is the lower bound just helpful/useful to set a target when trying to show an upper bound?
Reference:
From page 41 of this book pdf version
https://pdfs.semanticscholar.org/e923/9469aba4bccf3e36d1c27894721e8dbefc44.pdf
machine-learning pac-learning vc-theory
asked Apr 10 at 0:44
ML studentML student
594
$endgroup$
In the book "Foundations of Machine Learning" there are examples of proving the VC dimensions for various hypotheses, e.g., for axis-aligned rectangles, convex polygons, sine functions, hyperplanes, etc.
All proofs first derive a lower bound, and then show an upper bound. However, why not just derive the upper bound since the definition of VC dimension only cares about the "largest" set that can be shattered by hypothesis set $mathcalH$? Since all examples ends up with a lower bound matching the upper bound, is the lower bound just helpful/useful to set a target when trying to show an upper bound?
Reference:
From page 41 of this book pdf version
https://pdfs.semanticscholar.org/e923/9469aba4bccf3e36d1c27894721e8dbefc44.pdf
machine-learning pac-learning vc-theory
machine-learning pac-learning vc-theory
asked Apr 10 at 0:44
ML studentML student
594
asked Apr 10 at 0:44
ML studentML student
594
asked Apr 10 at 0:44
ML studentML student
594
asked Apr 10 at 0:44
ML studentML student
594
asked Apr 10 at 0:44
ML studentML student
594
594
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Lets use the quotes from the book.
To give an upper bound, we need to prove that no set $S$ of cardinality
$d + 1$ can be shattered by $H$
By doing this, we are proving that $textVCdim(H) < d+1$, but it does not necessarily mean $textVCdim(H) = d$. For example, we may go for an easier-to-prove failure like sets with $2d+1$ members, and consequently prove $textVCdim(H) < 2d+1$, although we know $textVCdim(H) = d$. Therefore:
To give a lower bound $d$ for $textVCdim(H)$, it suffices to show that a set $S$
of cardinality $d$ can be shattered by $H$
We need to prove the lower bound as well to show that $d le textVCdim(H) < d+1$, which implies $textVCdim(H) = d$. The last equality means $H$ can shatter any set $S$ of size $1$ to $d$.
Note that for the $2d+1$ example, we will fail to prove $2d le textVCdim(H)$, therefore $textVCdim(H) neq 2d$, and consequently we must try to prove a smaller (probably harder to prove) upper bound $d+1$.
answered Apr 10 at 12:29
EsmailianEsmailian
4,114422
$endgroup$
$begingroup$
Thank you!! Now I understand I had some misunderstandings of the equations.
$endgroup$
– ML student
Apr 12 at 14:04
$begingroup$
@MLstudent My pleasure! Glad I could help.
$endgroup$
– Esmailian
Apr 12 at 14:10
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "557"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fdatascience.stackexchange.com%2fquestions%2f49004%2fwhy-is-a-lower-bound-necessary-in-proofs-of-vc-dimensions-for-various-examples-o%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Lets use the quotes from the book.
To give an upper bound, we need to prove that no set $S$ of cardinality
$d + 1$ can be shattered by $H$
By doing this, we are proving that $textVCdim(H) < d+1$, but it does not necessarily mean $textVCdim(H) = d$. For example, we may go for an easier-to-prove failure like sets with $2d+1$ members, and consequently prove $textVCdim(H) < 2d+1$, although we know $textVCdim(H) = d$. Therefore:
To give a lower bound $d$ for $textVCdim(H)$, it suffices to show that a set $S$
of cardinality $d$ can be shattered by $H$
We need to prove the lower bound as well to show that $d le textVCdim(H) < d+1$, which implies $textVCdim(H) = d$. The last equality means $H$ can shatter any set $S$ of size $1$ to $d$.
Note that for the $2d+1$ example, we will fail to prove $2d le textVCdim(H)$, therefore $textVCdim(H) neq 2d$, and consequently we must try to prove a smaller (probably harder to prove) upper bound $d+1$.
answered Apr 10 at 12:29
EsmailianEsmailian
4,114422
$endgroup$
$begingroup$
Thank you!! Now I understand I had some misunderstandings of the equations.
$endgroup$
– ML student
Apr 12 at 14:04
$begingroup$
@MLstudent My pleasure! Glad I could help.
$endgroup$
– Esmailian
Apr 12 at 14:10
add a comment |
$begingroup$
Lets use the quotes from the book.
To give an upper bound, we need to prove that no set $S$ of cardinality
$d + 1$ can be shattered by $H$
By doing this, we are proving that $textVCdim(H) < d+1$, but it does not necessarily mean $textVCdim(H) = d$. For example, we may go for an easier-to-prove failure like sets with $2d+1$ members, and consequently prove $textVCdim(H) < 2d+1$, although we know $textVCdim(H) = d$. Therefore:
To give a lower bound $d$ for $textVCdim(H)$, it suffices to show that a set $S$
of cardinality $d$ can be shattered by $H$
We need to prove the lower bound as well to show that $d le textVCdim(H) < d+1$, which implies $textVCdim(H) = d$. The last equality means $H$ can shatter any set $S$ of size $1$ to $d$.
Note that for the $2d+1$ example, we will fail to prove $2d le textVCdim(H)$, therefore $textVCdim(H) neq 2d$, and consequently we must try to prove a smaller (probably harder to prove) upper bound $d+1$.
answered Apr 10 at 12:29
EsmailianEsmailian
4,114422
$endgroup$
$begingroup$
Thank you!! Now I understand I had some misunderstandings of the equations.
$endgroup$
– ML student
Apr 12 at 14:04
$begingroup$
@MLstudent My pleasure! Glad I could help.
$endgroup$
– Esmailian
Apr 12 at 14:10
add a comment |
$begingroup$
Lets use the quotes from the book.
To give an upper bound, we need to prove that no set $S$ of cardinality
$d + 1$ can be shattered by $H$
By doing this, we are proving that $textVCdim(H) < d+1$, but it does not necessarily mean $textVCdim(H) = d$. For example, we may go for an easier-to-prove failure like sets with $2d+1$ members, and consequently prove $textVCdim(H) < 2d+1$, although we know $textVCdim(H) = d$. Therefore:
To give a lower bound $d$ for $textVCdim(H)$, it suffices to show that a set $S$
of cardinality $d$ can be shattered by $H$
We need to prove the lower bound as well to show that $d le textVCdim(H) < d+1$, which implies $textVCdim(H) = d$. The last equality means $H$ can shatter any set $S$ of size $1$ to $d$.
Note that for the $2d+1$ example, we will fail to prove $2d le textVCdim(H)$, therefore $textVCdim(H) neq 2d$, and consequently we must try to prove a smaller (probably harder to prove) upper bound $d+1$.
answered Apr 10 at 12:29
EsmailianEsmailian
4,114422
$endgroup$
Lets use the quotes from the book.
To give an upper bound, we need to prove that no set $S$ of cardinality
$d + 1$ can be shattered by $H$
By doing this, we are proving that $textVCdim(H) < d+1$, but it does not necessarily mean $textVCdim(H) = d$. For example, we may go for an easier-to-prove failure like sets with $2d+1$ members, and consequently prove $textVCdim(H) < 2d+1$, although we know $textVCdim(H) = d$. Therefore:
To give a lower bound $d$ for $textVCdim(H)$, it suffices to show that a set $S$
of cardinality $d$ can be shattered by $H$
We need to prove the lower bound as well to show that $d le textVCdim(H) < d+1$, which implies $textVCdim(H) = d$. The last equality means $H$ can shatter any set $S$ of size $1$ to $d$.
Note that for the $2d+1$ example, we will fail to prove $2d le textVCdim(H)$, therefore $textVCdim(H) neq 2d$, and consequently we must try to prove a smaller (probably harder to prove) upper bound $d+1$.
answered Apr 10 at 12:29
EsmailianEsmailian
4,114422
edited Apr 12 at 14:08
answered Apr 10 at 12:29
EsmailianEsmailian
4,114422
answered Apr 10 at 12:29
EsmailianEsmailian
4,114422
answered Apr 10 at 12:29
EsmailianEsmailian
4,114422
4,114422
$begingroup$
Thank you!! Now I understand I had some misunderstandings of the equations.
$endgroup$
– ML student
Apr 12 at 14:04
$begingroup$
@MLstudent My pleasure! Glad I could help.
$endgroup$
– Esmailian
Apr 12 at 14:10
add a comment |
$begingroup$
Thank you!! Now I understand I had some misunderstandings of the equations.
$endgroup$
– ML student
Apr 12 at 14:04
$begingroup$
@MLstudent My pleasure! Glad I could help.
$endgroup$
– Esmailian
Apr 12 at 14:10
$begingroup$
Thank you!! Now I understand I had some misunderstandings of the equations.
$endgroup$
– ML student
Apr 12 at 14:04
$begingroup$
Thank you!! Now I understand I had some misunderstandings of the equations.
$endgroup$
– ML student
Apr 12 at 14:04
$begingroup$
@MLstudent My pleasure! Glad I could help.
$endgroup$
– Esmailian
Apr 12 at 14:10
$begingroup$
@MLstudent My pleasure! Glad I could help.
$endgroup$
– Esmailian
Apr 12 at 14:10
add a comment |
Thanks for contributing an answer to Data Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fdatascience.stackexchange.com%2fquestions%2f49004%2fwhy-is-a-lower-bound-necessary-in-proofs-of-vc-dimensions-for-various-examples-o%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
