Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 637
ybdesire Avatar asked Nov 21 '16 08:11

ybdesire


1 Answers

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

like image 195
Martin Thoma Avatar answered Oct 14 '22 21:10

Martin Thoma