Answers.Body: <p>The problem of multiple existing solutions is not uniquely related to the optimization algorithm of choice, it is actually many times related to the problem itself. More precisely, it is a direct consequence of the <a href="https://en.wikipedia.org/wiki/Rouch%C3%A9%E2%80%93Capelli_theorem" rel="nofollow noreferrer">Rouché–Capelli theorem</a>.</p>
  <p>A simple or multilayer perceptron is nothing but a system of linear equations, in which the input set represent the coefficient matrix, the input set plus the targets represent the augmented matrix and the perceptron weights are the free parameters to solve.</p>
  <p>As the theorem states, if the 2 matrices have the same rank, there is at least one solution, and if the rank of the 2 matrices is less than the number of unknowns, the solutions will be infinite in number.</p>
  <p>Let's consider a very simple function, the XOR function in the image below. We can see that both, the coefficient matrix (input 1 + input 2 column) and the augmented matrix (input1 + input 2 + output) have rank 3, since row 1 and row 3 are not indipendent (i.e. I can rewrite one as a multiple of the other). Moreover, we can see that the number of unknowns is 4, less than the rank. Hence there are infinite solutions, because once I find a solution, for the weights for row 1, I can write infinite sets of weights, multiples of the solution found, that will work as parameters for row 3.</p>
  <p>Note that the theorem talks only about coefficients, i.e. known variables, so this result and test holds regardless of the learned weights and therefore regardless of the optimization algorithm of choice.</p>
  <p><a href="https://i.sstatic.net/WCl2j.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/WCl2j.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-23T18:17:21.833Z
Answers.LastActivityDate: 2022-05-23T18:17:21.833Z
Answers.UserDisplayName: Edoardo Guerriero
Answers.Body: <p>Like what was mentioned by Edoardo, absent some other constraint, if your data is infinitely separable, then you can find an infinite number of separating hyperplanes. The perceptron algorithm will just find <em>a</em> hyperplane.</p>
  <p>However there are constraints you can put on your model such that there only exists a single separating hyperplane.</p>
  <p>The most famous is probably the support vector machine. Here, we assume that the &quot;best&quot; hyperplane should also be the one that's the furthest from the closest points in each class (i.e., the <a href="https://www.sciencedirect.com/topics/computer-science/maximum-margin-hyperplane" rel="nofollow noreferrer">maximum-margin hyperplane</a>). <a href="https://proceedings.neurips.cc/paper_files/paper/1999/file/c4492cbe90fbdbf88a5aec486aa81ed5-Paper.pdf" rel="nofollow noreferrer">There are conditions in which this hyperplane is unique.</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-16T03:54:36.067Z
Answers.LastActivityDate: 2023-10-16T03:54:36.067Z
Answers.UserDisplayName: Alexander Wan
Body: <p>The perceptron convergence algorithm given below ensures the convergence of weights of the perceptron provided enough data points and iterations.</p>
  <p><a href="https://i.sstatic.net/IYcO2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/IYcO2.png" alt="enter image description here" /></a></p>
  <p>Although it ensures convergence by finally getting a decision hyperplane that can separate positive samples (P) from negative samples N. It <a href="https://www.sciencedirect.com/topics/computer-science/perceptron-algorithm" rel="nofollow noreferrer">does not ensure the uniqueness</a> of the decision hyperplane.</p>
  <blockquote>
  <p>The solution is not unique, because there are more than one
  hyperplanes separating two linearly separable classes.</p>
  </blockquote>
  <p>Are there any variants to this algorithm in the literature that are capable of ensuring uniqueness?</p>
  
Tags: <reference-request><algorithm-request><convergence><perceptron>
Title: Is there any variant of perceptron convergence algorithm that ensures uniqueness?
UserDisplayName: hanugm
ThreadText: # Is there any variant of perceptron convergence algorithm that ensures uniqueness?
  
  (Asked by: username_0 on 2022-05-22)
  
  The perceptron convergence algorithm given below ensures the convergence of weights of the perceptron provided enough data points and iterations.
  
  [![enter image description here](https://i.sstatic.net/IYcO2.png)](https://i.sstatic.net/IYcO2.png)
  
  Although it ensures convergence by finally getting a decision hyperplane that can separate positive samples (P) from negative samples N. It [does not ensure the uniqueness](https://www.sciencedirect.com/topics/computer-science/perceptron-algorithm) of the decision hyperplane.
  
  > The solution is not unique, because there are more than one
  > hyperplanes separating two linearly separable classes.
  
  Are there any variants to this algorithm in the literature that are capable of ensuring uniqueness?
  
  **Tags:** reference-request, algorithm-request, convergence, perceptron
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2022-05-23. Score: 0
  
  The problem of multiple existing solutions is not uniquely related to the optimization algorithm of choice, it is actually many times related to the problem itself. More precisely, it is a direct consequence of the [Rouché–Capelli theorem](https://en.wikipedia.org/wiki/Rouch%C3%A9%E2%80%93Capelli_theorem).
  
  A simple or multilayer perceptron is nothing but a system of linear equations, in which the input set represent the coefficient matrix, the input set plus the targets represent the augmented matrix and the perceptron weights are the free parameters to solve.
  
  As the theorem states, if the 2 matrices have the same rank, there is at least one solution, and if the rank of the 2 matrices is less than the number of unknowns, the solutions will be infinite in number.
  
  Let's consider a very simple function, the XOR function in the image below. We can see that both, the coefficient matrix (input 1 + input 2 column) and the augmented matrix (input1 + input 2 + output) have rank 3, since row 1 and row 3 are not indipendent (i.e. I can rewrite one as a multiple of the other). Moreover, we can see that the number of unknowns is 4, less than the rank. Hence there are infinite solutions, because once I find a solution, for the weights for row 1, I can write infinite sets of weights, multiples of the solution found, that will work as parameters for row 3.
  
  Note that the theorem talks only about coefficients, i.e. known variables, so this result and test holds regardless of the learned weights and therefore regardless of the optimization algorithm of choice.
  
  [![enter image description here](https://i.sstatic.net/WCl2j.png)](https://i.sstatic.net/WCl2j.png)
  
  
  ---
  
  ### Answer by username_2 on 2023-10-16. Score: 0
  
  Like what was mentioned by Edoardo, absent some other constraint, if your data is infinitely separable, then you can find an infinite number of separating hyperplanes. The perceptron algorithm will just find *a* hyperplane.
  
  However there are constraints you can put on your model such that there only exists a single separating hyperplane.
  
  The most famous is probably the support vector machine. Here, we assume that the "best" hyperplane should also be the one that's the furthest from the closest points in each class (i.e., the [maximum-margin hyperplane](https://www.sciencedirect.com/topics/computer-science/maximum-margin-hyperplane)). [There are conditions in which this hyperplane is unique.](https://proceedings.neurips.cc/paper_files/paper/1999/file/c4492cbe90fbdbf88a5aec486aa81ed5-Paper.pdf)
  
  
  ---
  
  