# Suggest an exhaustive procedure that will find a separating vector for linearly separable pattern in a finite number of steps

I read in a pattern classification text, that if we consider weight vectors whose components are integer valued, the perceptron procedure would terminate in a finite number of steps.

What is the intuition and theory behind this?

EDIT: It is a homework problem from the text book Pattern classification by Duda, Hart, Stork, and I just wanted a hint, so posted the above query. Here is the actual homework problem:

Let ${y_{1},...,y_{n}}$ be a finite set of linearly separable samples in d dimensions. Suggest an exhaustive procedure that will find a separating vector in a finite number of steps. (You might wish to consider weight vectors whose components are integer valued.)

• Can you add some more details? I don't know how exactly you would apply the learning rule to only allow for integer values. How exactly do you round off etc.? Aug 29, 2011 at 6:56
• I have updated my question with more details Aug 29, 2011 at 14:44
• It seems you could use the result of your previous question to develop a brute force $O((n-d-1)\binom{n}{d+1})$ algorithm.
– whuber
Aug 29, 2011 at 14:53
• Thanks! Will post the post the solution, to close the question. Sep 5, 2011 at 6:35
• – Sycorax
Jul 8, 2018 at 1:27