Answers.Body: <p>I think I have a counterexample:</p>
  <p><span class="math-container">$$
  X=(0,1,0,1)\\
  Y=(0, 0, 1,1)
  $$</span></p>
  <p>No polynomial can separate the values of <span class="math-container">$Y$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-12T00:46:16.403Z
Answers.LastActivityDate: 2022-08-12T00:46:16.403Z
Answers.UserDisplayName: Dave
Answers.Body: <p>Unless I'm missing something I think you're simply looking for the <a href="https://en.wikipedia.org/wiki/Rouch%C3%A9%E2%80%93Capelli_theorem" rel="nofollow noreferrer">Rouche Capelli theorem</a>.</p>
  <p>A polynomial classifier is just a set of linear equations made of feature vectors and coefficients (parameters) vectors. So to know if a solution exists you would have to compute the rank of the classifier coefficient matrix and expanded matrix and compare their ranks.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-11T20:32:36.263Z
Answers.Text: Thanks but unless I misunderstand you, I am interested in the powers and limits of polynomial classifiers to solve binary classification tasks. For example, a set of data labelled such that (0,0) and (1,1) are positive and yet (0,1) and (1,0) are labelled negative, cannot admit of a linear classifier but needs a polynomial one.
Answers.UserDisplayName: letsmakemuffinstogether
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-12T05:36:18.773Z
Answers.Text: linear or polynomial, a classifier is anyway solved as a set of linear equations, with respect to the coefficient we are solving for. So the theorem should still be applicable.
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-12T05:42:39.447Z
Answers.Text: to rephrase the idea of the theorem, it's not about dividing the data, that's always possible in theory, cause worst case scenario I can always define n hyper planes, one for each point in my data. It's about how many coefficient (or equations) I can define based on my data that limit the expressive power of a classifier.
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-11T17:52:40.260Z
Answers.LastActivityDate: 2022-08-11T17:52:40.260Z
Answers.UserDisplayName: Edoardo Guerriero
Body: <p>Does anyone know if there is a theorem or counterexample establishing whether or not for any given binary classification task in some finite (possibly large) dimensional vector space of attributes, that there exists a polynomial classifier that can form a hyperplane sorting all the positive from negatively labelled data points?</p>
  <p>To clarify, I know that if a dataset is linearly separable, then we can find such a linear classifier. But my question is more general and asks if without knowing beforehand whether a dataset is separable at all, can we know ahead of time if there exists a polynomial classifier for any n-dimensional vector space of data points?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-17T01:05:59.090Z
Comments.Text: they are all wrong, check this answer https://stats.stackexchange.com/questions/549852/can-any-data-be-learned-using-polynomial-logistic-regression (you can obviously ignore the "logistic" part since it's just used to transform it to probability.. the decision boundary is still made by a polynomial function, thus it still holds)
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-01-04T12:11:14.797Z
Comments.Text: [Stone-Weierstrass?](https://en.wikipedia.org/wiki/Stone–Weierstrass_theorem)
Comments.UserDisplayName: Dave
Tags: <datasets><generalization>
Title: Master theorem about polynomial classifiers?
UserDisplayName: letsmakemuffinstogether
ThreadText: # Master theorem about polynomial classifiers?
  
  (Asked by: username_0 on 2022-08-11)
  
  Does anyone know if there is a theorem or counterexample establishing whether or not for any given binary classification task in some finite (possibly large) dimensional vector space of attributes, that there exists a polynomial classifier that can form a hyperplane sorting all the positive from negatively labelled data points?
  
  To clarify, I know that if a dataset is linearly separable, then we can find such a linear classifier. But my question is more general and asks if without knowing beforehand whether a dataset is separable at all, can we know ahead of time if there exists a polynomial classifier for any n-dimensional vector space of data points?
  
  **Tags:** datasets, generalization
  > **Comments:**
  > **username_1**: they are all wrong, check this answer https://stats.stackexchange.com/questions/549852/can-any-data-be-learned-using-polynomial-logistic-regression (you can obviously ignore the "logistic" part since it's just used to transform it to probability.. the decision boundary is still made by a polynomial function, thus it still holds)  
  > **username_2**: [Stone-Weierstrass?](https://en.wikipedia.org/wiki/Stone–Weierstrass_theorem)  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2022-08-12. Score: 0
  
  I think I have a counterexample:
  
  $$
  X=(0,1,0,1)\\
  Y=(0, 0, 1,1)
  $$
  
  No polynomial can separate the values of $Y$.
  
  
  ---
  
  ### Answer by username_3 on 2022-08-11. Score: 0
  
  Unless I'm missing something I think you're simply looking for the [Rouche Capelli theorem](https://en.wikipedia.org/wiki/Rouch%C3%A9%E2%80%93Capelli_theorem).
  
  A polynomial classifier is just a set of linear equations made of feature vectors and coefficients (parameters) vectors. So to know if a solution exists you would have to compute the rank of the classifier coefficient matrix and expanded matrix and compare their ranks.
  
  > **Comments:**
  > **username_0**: Thanks but unless I misunderstand you, I am interested in the powers and limits of polynomial classifiers to solve binary classification tasks. For example, a set of data labelled such that (0,0) and (1,1) are positive and yet (0,1) and (1,0) are labelled negative, cannot admit of a linear classifier but needs a polynomial one.  
  > **username_3**: linear or polynomial, a classifier is anyway solved as a set of linear equations, with respect to the coefficient we are solving for. So the theorem should still be applicable.  
  > **username_3**: to rephrase the idea of the theorem, it's not about dividing the data, that's always possible in theory, cause worst case scenario I can always define n hyper planes, one for each point in my data. It's about how many coefficient (or equations) I can define based on my data that limit the expressive power of a classifier.  
  
  ---
  
  