Vapnik-Chervonenkis theory: growth function
A classification problem is considered with observations $x in mathbb{R}^2$ and responses $y in {0,1}$. There is a set of axis-aligned rectangle classifiers $F$. Particularly, сlassifier $f_{a,b} in F$ is defined so: if $a_1 le x_1 le b_1 ,space a_2 le x_2 le b_2$ $f(x)=1$ else $f(x)=0$.
The problem is to determine Vapnic-Chervonenkis dimension and growth function for set $F$.
I found here that VC-dimension is 4. But I have no idea how to find growth function.
machine-learning
asked Jan 16 '14 at 20:11
SergeySergey
42
add a comment |
A classification problem is considered with observations $x in mathbb{R}^2$ and responses $y in {0,1}$. There is a set of axis-aligned rectangle classifiers $F$. Particularly, сlassifier $f_{a,b} in F$ is defined so: if $a_1 le x_1 le b_1 ,space a_2 le x_2 le b_2$ $f(x)=1$ else $f(x)=0$.
The problem is to determine Vapnic-Chervonenkis dimension and growth function for set $F$.
I found here that VC-dimension is 4. But I have no idea how to find growth function.
machine-learning
asked Jan 16 '14 at 20:11
SergeySergey
42
add a comment |
A classification problem is considered with observations $x in mathbb{R}^2$ and responses $y in {0,1}$. There is a set of axis-aligned rectangle classifiers $F$. Particularly, сlassifier $f_{a,b} in F$ is defined so: if $a_1 le x_1 le b_1 ,space a_2 le x_2 le b_2$ $f(x)=1$ else $f(x)=0$.
The problem is to determine Vapnic-Chervonenkis dimension and growth function for set $F$.
I found here that VC-dimension is 4. But I have no idea how to find growth function.
machine-learning
asked Jan 16 '14 at 20:11
SergeySergey
42
A classification problem is considered with observations $x in mathbb{R}^2$ and responses $y in {0,1}$. There is a set of axis-aligned rectangle classifiers $F$. Particularly, сlassifier $f_{a,b} in F$ is defined so: if $a_1 le x_1 le b_1 ,space a_2 le x_2 le b_2$ $f(x)=1$ else $f(x)=0$.
The problem is to determine Vapnic-Chervonenkis dimension and growth function for set $F$.
I found here that VC-dimension is 4. But I have no idea how to find growth function.
machine-learning
machine-learning
asked Jan 16 '14 at 20:11
SergeySergey
42
asked Jan 16 '14 at 20:11
SergeySergey
42
asked Jan 16 '14 at 20:11
SergeySergey
42
asked Jan 16 '14 at 20:11
SergeySergey
42
asked Jan 16 '14 at 20:11
SergeySergey
42
42
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
The VC-dimension is the size of the largest set
that can be fully shattered by H an Hypothesis set.
Purely combinatorial notion.
VCdim(H) = max{m: H (m)=2**m}.
http://www.cs.nyu.edu/~mohri/mls/lecture_3.pdf
As you can see in this pdf, page 25, for one axis aaligned rectangle the VC-dim is 4
"No set of five points can be shattered: label negatively the point that is not near the sides"
But, in your example there seems to be 2 rectangles so you can shatter more complex point configurations, the VC dim will be higher.
answered Oct 22 '14 at 6:13
mrautomrauto
1
In my example there is one rectangle too. It seems that there is no difference between my example and example in pdf you referenced.
– Sergey
Oct 24 '14 at 16:14
you're right, you have a single axis aligned rectangle, my bad. in this case, the break point is at 5, (first counter example: 5points not shatterable by rectangle by labelling nega tive the point inside the 4 others) Thus the VC dimension is 4 and for m points the growth function will be O(m4) which is much less than 2m after the break point (inclusive) The exact polynomial of degree 4 is not necessarily obvious... (combinatorics)
– mrauto
Nov 5 '14 at 7:31
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f640907%2fvapnik-chervonenkis-theory-growth-function%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
The VC-dimension is the size of the largest set
that can be fully shattered by H an Hypothesis set.
Purely combinatorial notion.
VCdim(H) = max{m: H (m)=2**m}.
http://www.cs.nyu.edu/~mohri/mls/lecture_3.pdf
As you can see in this pdf, page 25, for one axis aaligned rectangle the VC-dim is 4
"No set of five points can be shattered: label negatively the point that is not near the sides"
But, in your example there seems to be 2 rectangles so you can shatter more complex point configurations, the VC dim will be higher.
answered Oct 22 '14 at 6:13
mrautomrauto
1
In my example there is one rectangle too. It seems that there is no difference between my example and example in pdf you referenced.
– Sergey
Oct 24 '14 at 16:14
you're right, you have a single axis aligned rectangle, my bad. in this case, the break point is at 5, (first counter example: 5points not shatterable by rectangle by labelling nega tive the point inside the 4 others) Thus the VC dimension is 4 and for m points the growth function will be O(m4) which is much less than 2m after the break point (inclusive) The exact polynomial of degree 4 is not necessarily obvious... (combinatorics)
– mrauto
Nov 5 '14 at 7:31
add a comment |
The VC-dimension is the size of the largest set
that can be fully shattered by H an Hypothesis set.
Purely combinatorial notion.
VCdim(H) = max{m: H (m)=2**m}.
http://www.cs.nyu.edu/~mohri/mls/lecture_3.pdf
As you can see in this pdf, page 25, for one axis aaligned rectangle the VC-dim is 4
"No set of five points can be shattered: label negatively the point that is not near the sides"
But, in your example there seems to be 2 rectangles so you can shatter more complex point configurations, the VC dim will be higher.
answered Oct 22 '14 at 6:13
mrautomrauto
1
In my example there is one rectangle too. It seems that there is no difference between my example and example in pdf you referenced.
– Sergey
Oct 24 '14 at 16:14
you're right, you have a single axis aligned rectangle, my bad. in this case, the break point is at 5, (first counter example: 5points not shatterable by rectangle by labelling nega tive the point inside the 4 others) Thus the VC dimension is 4 and for m points the growth function will be O(m4) which is much less than 2m after the break point (inclusive) The exact polynomial of degree 4 is not necessarily obvious... (combinatorics)
– mrauto
Nov 5 '14 at 7:31
add a comment |
The VC-dimension is the size of the largest set
that can be fully shattered by H an Hypothesis set.
Purely combinatorial notion.
VCdim(H) = max{m: H (m)=2**m}.
http://www.cs.nyu.edu/~mohri/mls/lecture_3.pdf
As you can see in this pdf, page 25, for one axis aaligned rectangle the VC-dim is 4
"No set of five points can be shattered: label negatively the point that is not near the sides"
But, in your example there seems to be 2 rectangles so you can shatter more complex point configurations, the VC dim will be higher.
answered Oct 22 '14 at 6:13
mrautomrauto
1
The VC-dimension is the size of the largest set
that can be fully shattered by H an Hypothesis set.
Purely combinatorial notion.
VCdim(H) = max{m: H (m)=2**m}.
http://www.cs.nyu.edu/~mohri/mls/lecture_3.pdf
As you can see in this pdf, page 25, for one axis aaligned rectangle the VC-dim is 4
"No set of five points can be shattered: label negatively the point that is not near the sides"
But, in your example there seems to be 2 rectangles so you can shatter more complex point configurations, the VC dim will be higher.
answered Oct 22 '14 at 6:13
mrautomrauto
1
answered Oct 22 '14 at 6:13
mrautomrauto
1
answered Oct 22 '14 at 6:13
mrautomrauto
1
answered Oct 22 '14 at 6:13
mrautomrauto
1
1
In my example there is one rectangle too. It seems that there is no difference between my example and example in pdf you referenced.
– Sergey
Oct 24 '14 at 16:14
you're right, you have a single axis aligned rectangle, my bad. in this case, the break point is at 5, (first counter example: 5points not shatterable by rectangle by labelling nega tive the point inside the 4 others) Thus the VC dimension is 4 and for m points the growth function will be O(m4) which is much less than 2m after the break point (inclusive) The exact polynomial of degree 4 is not necessarily obvious... (combinatorics)
– mrauto
Nov 5 '14 at 7:31
add a comment |
In my example there is one rectangle too. It seems that there is no difference between my example and example in pdf you referenced.
– Sergey
Oct 24 '14 at 16:14
you're right, you have a single axis aligned rectangle, my bad. in this case, the break point is at 5, (first counter example: 5points not shatterable by rectangle by labelling nega tive the point inside the 4 others) Thus the VC dimension is 4 and for m points the growth function will be O(m4) which is much less than 2m after the break point (inclusive) The exact polynomial of degree 4 is not necessarily obvious... (combinatorics)
– mrauto
Nov 5 '14 at 7:31
In my example there is one rectangle too. It seems that there is no difference between my example and example in pdf you referenced.
– Sergey
Oct 24 '14 at 16:14
In my example there is one rectangle too. It seems that there is no difference between my example and example in pdf you referenced.
– Sergey
Oct 24 '14 at 16:14
you're right, you have a single axis aligned rectangle, my bad. in this case, the break point is at 5, (first counter example: 5points not shatterable by rectangle by labelling nega tive the point inside the 4 others) Thus the VC dimension is 4 and for m points the growth function will be O(m4) which is much less than 2m after the break point (inclusive) The exact polynomial of degree 4 is not necessarily obvious... (combinatorics)
– mrauto
Nov 5 '14 at 7:31
you're right, you have a single axis aligned rectangle, my bad. in this case, the break point is at 5, (first counter example: 5points not shatterable by rectangle by labelling nega tive the point inside the 4 others) Thus the VC dimension is 4 and for m points the growth function will be O(m4) which is much less than 2m after the break point (inclusive) The exact polynomial of degree 4 is not necessarily obvious... (combinatorics)
– mrauto
Nov 5 '14 at 7:31
add a comment |
Thanks for contributing an answer to Mathematics 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fmath.stackexchange.com%2fquestions%2f640907%2fvapnik-chervonenkis-theory-growth-function%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
