My understanding is that the Perceptron Learning Algorithm:

  • will not converge if the data is not linearly separable.
  • might take exponentially many iterations, even if the data is linearly separable.

I'm wondering if, after $k$ steps, anything can be said about the probability that the data is linearly separable?

  • $\begingroup$ Interesting thought, but my hunch is you'll probably have to make some fairly strong assumptions on the distribution of the training data to say anything like this. $\endgroup$ – Dougal Jul 29 '15 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.