CODEWITHSUNDEEP
machine-learning
ybdesire
ybdesire

Reputation: 1713

Why the VC dimension of 2D perceptron is 3?

If three points in one line as below, how can the 2D perceptron classify this 3 points?

enter image description here

Upvotes: 8

Views: 1536

Answers (1)

Martin Thoma
Martin Thoma

Reputation: 136665

The VC dimension of a classifier is determined the following way:

VC = 1
found = False
while True:
    for point_distribution in all possible point distributions of VC+1 points:
        allcorrect = True
        for classdist in every way the classes could be assigned to the classes:
            if classifier can't classify everything correct:
                allcorrect = False
                break
        if allcorrect:
            VC += 1
            continue
    break

So there has only to be one way to place three points such that all possible class distributions among this point-placement can be classified the correct way.

If you don't place the three points on a line, the perception gets it right. But there is no way to get the perception classify all possible class distributions of 4 points, no matter how you place the points

Upvotes: 4

Related Questions