Mixing
SVM “kernel trick” and linearly separable sets of points
$begingroup$
Background info: in Machine Learning there's something called an SVM (Support Vector Machine) that employs a "kernel trick" to map sets of points to a higher dimension in order to find a hyperplane that linearly separates the sets of points.
For example, suppose a set of 2D "green" points are inside a unit circle centered at the origin, and a set of 2D "red" points are in the annulus (also centered at the origin) whose inner/outer radius is 2 and 3.
Then an SVM kernel can map these sets of points to a paraboloid of revolution in 3D, and the plane with equation z = 1.5 would be the "maximally separating" hyperplane.
The interesting fact is that the kernel trick works for "nested" sets of points (as in the preceding example).
With the preceding in mind:
a) under which constraints can sets (clusters) of n-dimensional points be mapped to (n+1)-dimensional points and be assured of finding a hyperplane that linearly separates the sets of points?
b) would a) be true for sets of (n+k)-dim points where k>=2?
c) would a) be true in the case of any arbitrary collection of compact and connected sets (of 2D points) that are "non-nested" and pairwise non-intersecting?
There are variations of the preceding questions but these are enough to start with:)
Btw I'm not sure if this question is best answered in differential geometry or differential topology (or perhaps something else?)
geometry differential
asked Jan 30 at 20:34
Oswald CampesatoOswald Campesato
1
$endgroup$
add a comment |
$begingroup$
Background info: in Machine Learning there's something called an SVM (Support Vector Machine) that employs a "kernel trick" to map sets of points to a higher dimension in order to find a hyperplane that linearly separates the sets of points.
For example, suppose a set of 2D "green" points are inside a unit circle centered at the origin, and a set of 2D "red" points are in the annulus (also centered at the origin) whose inner/outer radius is 2 and 3.
Then an SVM kernel can map these sets of points to a paraboloid of revolution in 3D, and the plane with equation z = 1.5 would be the "maximally separating" hyperplane.
The interesting fact is that the kernel trick works for "nested" sets of points (as in the preceding example).
With the preceding in mind:
a) under which constraints can sets (clusters) of n-dimensional points be mapped to (n+1)-dimensional points and be assured of finding a hyperplane that linearly separates the sets of points?
b) would a) be true for sets of (n+k)-dim points where k>=2?
c) would a) be true in the case of any arbitrary collection of compact and connected sets (of 2D points) that are "non-nested" and pairwise non-intersecting?
There are variations of the preceding questions but these are enough to start with:)
Btw I'm not sure if this question is best answered in differential geometry or differential topology (or perhaps something else?)
geometry differential
asked Jan 30 at 20:34
Oswald CampesatoOswald Campesato
1
$endgroup$
add a comment |
$begingroup$
Background info: in Machine Learning there's something called an SVM (Support Vector Machine) that employs a "kernel trick" to map sets of points to a higher dimension in order to find a hyperplane that linearly separates the sets of points.
For example, suppose a set of 2D "green" points are inside a unit circle centered at the origin, and a set of 2D "red" points are in the annulus (also centered at the origin) whose inner/outer radius is 2 and 3.
Then an SVM kernel can map these sets of points to a paraboloid of revolution in 3D, and the plane with equation z = 1.5 would be the "maximally separating" hyperplane.
The interesting fact is that the kernel trick works for "nested" sets of points (as in the preceding example).
With the preceding in mind:
a) under which constraints can sets (clusters) of n-dimensional points be mapped to (n+1)-dimensional points and be assured of finding a hyperplane that linearly separates the sets of points?
b) would a) be true for sets of (n+k)-dim points where k>=2?
c) would a) be true in the case of any arbitrary collection of compact and connected sets (of 2D points) that are "non-nested" and pairwise non-intersecting?
There are variations of the preceding questions but these are enough to start with:)
Btw I'm not sure if this question is best answered in differential geometry or differential topology (or perhaps something else?)
geometry differential
asked Jan 30 at 20:34
Oswald CampesatoOswald Campesato
1
$endgroup$
Background info: in Machine Learning there's something called an SVM (Support Vector Machine) that employs a "kernel trick" to map sets of points to a higher dimension in order to find a hyperplane that linearly separates the sets of points.
For example, suppose a set of 2D "green" points are inside a unit circle centered at the origin, and a set of 2D "red" points are in the annulus (also centered at the origin) whose inner/outer radius is 2 and 3.
Then an SVM kernel can map these sets of points to a paraboloid of revolution in 3D, and the plane with equation z = 1.5 would be the "maximally separating" hyperplane.
The interesting fact is that the kernel trick works for "nested" sets of points (as in the preceding example).
With the preceding in mind:
a) under which constraints can sets (clusters) of n-dimensional points be mapped to (n+1)-dimensional points and be assured of finding a hyperplane that linearly separates the sets of points?
b) would a) be true for sets of (n+k)-dim points where k>=2?
c) would a) be true in the case of any arbitrary collection of compact and connected sets (of 2D points) that are "non-nested" and pairwise non-intersecting?
There are variations of the preceding questions but these are enough to start with:)
Btw I'm not sure if this question is best answered in differential geometry or differential topology (or perhaps something else?)
geometry differential
geometry differential
asked Jan 30 at 20:34
Oswald CampesatoOswald Campesato
1
asked Jan 30 at 20:34
Oswald CampesatoOswald Campesato
1
asked Jan 30 at 20:34
Oswald CampesatoOswald Campesato
1
asked Jan 30 at 20:34
Oswald CampesatoOswald Campesato
1
asked Jan 30 at 20:34
Oswald CampesatoOswald Campesato
1
1
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
a) For this question, I think we can always find a mapping from dimension n to dimension n+1 that allows us to linearly separate two clusters. For example, we can keep the first n dimension and choose the last component of the $n+1$ dimension to be the label of the cluster (0 or 1). Then we can separate the two clusters with the hyperplane $x_{n+1} = frac{1}{2}$.
b) and c) are consequences of a) if I'm not wrong. For b) for example, we can just set the components in dimensions $n+2$, ..., $n+k$ to be equal to zero in the mapping of a).
answered Jan 30 at 21:20
Jonathan DJonathan D
1
$endgroup$
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%2f3094074%2fsvm-kernel-trick-and-linearly-separable-sets-of-points%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$
a) For this question, I think we can always find a mapping from dimension n to dimension n+1 that allows us to linearly separate two clusters. For example, we can keep the first n dimension and choose the last component of the $n+1$ dimension to be the label of the cluster (0 or 1). Then we can separate the two clusters with the hyperplane $x_{n+1} = frac{1}{2}$.
b) and c) are consequences of a) if I'm not wrong. For b) for example, we can just set the components in dimensions $n+2$, ..., $n+k$ to be equal to zero in the mapping of a).
answered Jan 30 at 21:20
Jonathan DJonathan D
1
$endgroup$
add a comment |
$begingroup$
a) For this question, I think we can always find a mapping from dimension n to dimension n+1 that allows us to linearly separate two clusters. For example, we can keep the first n dimension and choose the last component of the $n+1$ dimension to be the label of the cluster (0 or 1). Then we can separate the two clusters with the hyperplane $x_{n+1} = frac{1}{2}$.
b) and c) are consequences of a) if I'm not wrong. For b) for example, we can just set the components in dimensions $n+2$, ..., $n+k$ to be equal to zero in the mapping of a).
answered Jan 30 at 21:20
Jonathan DJonathan D
1
$endgroup$
add a comment |
$begingroup$
a) For this question, I think we can always find a mapping from dimension n to dimension n+1 that allows us to linearly separate two clusters. For example, we can keep the first n dimension and choose the last component of the $n+1$ dimension to be the label of the cluster (0 or 1). Then we can separate the two clusters with the hyperplane $x_{n+1} = frac{1}{2}$.
b) and c) are consequences of a) if I'm not wrong. For b) for example, we can just set the components in dimensions $n+2$, ..., $n+k$ to be equal to zero in the mapping of a).
answered Jan 30 at 21:20
Jonathan DJonathan D
1
$endgroup$
a) For this question, I think we can always find a mapping from dimension n to dimension n+1 that allows us to linearly separate two clusters. For example, we can keep the first n dimension and choose the last component of the $n+1$ dimension to be the label of the cluster (0 or 1). Then we can separate the two clusters with the hyperplane $x_{n+1} = frac{1}{2}$.
b) and c) are consequences of a) if I'm not wrong. For b) for example, we can just set the components in dimensions $n+2$, ..., $n+k$ to be equal to zero in the mapping of a).
answered Jan 30 at 21:20
Jonathan DJonathan D
1
answered Jan 30 at 21:20
Jonathan DJonathan D
1
answered Jan 30 at 21:20
Jonathan DJonathan D
1
answered Jan 30 at 21:20
Jonathan DJonathan D
1
1
add a comment |
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.
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%2f3094074%2fsvm-kernel-trick-and-linearly-separable-sets-of-points%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
