0
$\begingroup$

Suppose I have a linearly separable dataset, divide into training and validation sets. Will a perceptron learned on the training dataset be guaranteed to have no error on the training dataset and on the validation dataset?

$\endgroup$
  • $\begingroup$ Theoretically yes, you can create a perfectly linearly separable dataset and obtain such result. But you should definitely never expect such thing. In any real-life problem the data is noisy, for a bazilion of reasons, so no model is guaranteed to perform perfectly. To be sincere, unless I didn't understand your question well, it makes no sense at all. $\endgroup$ – Lucas Farias Feb 14 at 21:11
2
$\begingroup$

Your question, as I understand it, is this: Given a linearly separable data set, if a perceptron is trained on any subset of that data set, is the perceptron guaranteed to have a) 100% training accuracy and b) 100% test accuracy on the remaining data not in the training set?

Answer:

a) Since the data set is linearly separable, any subset of the data is also linearly separable. Thus, the perceptron is guaranteed to converge to a perfect solution on the training set. (https://en.wikipedia.org/wiki/Perceptron#Convergence)

b) No. Consider the following classification problem as a counterexample. The graph below shows a very simple linearly separable data set consisting of two classes of data points — red points and blue points. The black line highlights the linear separableness of the data.

Linearly separable data set

Now, since any subset of the points can be used for our training set, let’s suppose that the following two points ended up being our training set, taken from the data shown above.

Training set

Furthermore, suppose that the perceptron separates the classes in the following manner.

Training set, separated

Now the remaining points in the data set for validation or testing are the following, with the partition from training shown again as the same black line.

Entire data set again, with trained separation

Note that the test points are now falling on opposite sides of the line, so that the perceptron will fail on classifying both of those data points, because it did not select the best partition during training.

$\endgroup$
1
$\begingroup$

Perceptron is guaranteed to have zero-error when trained with a linearly separable dataset. It outputs a hyperplane that perfectly separates your training samples. But, this doesn't mean that you'll perfectly classify the validation set. Because the perceptron didn't see those samples, it's probable that it picked a bad decision boundary (among the possibly infinite choices), even if it perfectly works with the training set. And, I agree with @Lucas's comment that real-life datasets don't possess linear separability in general.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.