Suppose we have a number of items, each item belongs to either class 1 or class 2. Given the items only, we want to build an algorithm that will automatically classify these items into the respective classes after it has learnt from some examples. This is a simple classification problem. One of the earliest algorithms for classification is the Rosenblatt's Perceptron. The Perceptron algorithm tries to classify the items by building a hyperplane between the items of the two classes. In this talk we will prove a theorem due to Novikoff which asserts that, under some conditions, if the two classes can be separated by hyperplanes then the Perceptron algorithm will find one such hyperplane.
