Build (on paper) a k-th order perceptron that can distinguish a single simply-connected figure from multiple simply-connected figures. The input is an n-by-n binary array of pixels. The number k should be small, and the preprocessing should be a rather simple boolean operation. You can assume a blank border at the edge of the array of pixels, and you can assume that things do not ``just touch at a corner'' as in
* * * - - - - - * - - - - - - * * * - - - - * *(Do not view this hint unless you're really stuck!)
Prove that no k-th order perceptron can do n-bit parity. (Do not view this hint unless you're really stuck!)
Write a program that does online linear regression using LMS, and online linear discrimination using the Perceptron Learning Rule. Train using each rule on some synthetic data which you make. Visualize the results: successive locations of the weight vector in weight space; convergence rate (at various learning rates); successive locations of the discrimination plane in the input space, with the examplars shown; error rate as a function of number of training samples. To make visualization easier, confine yourself to 2D inputs (not including the bias.) Construct different synthetic datasets which vary in difficulty (eg how much play the discrimination plane has) and measure convergence time with the various datasets.