View Single Post
Old 10-17-2012, 01:57 PM
magdon's Avatar
magdon magdon is offline
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 597
Default Re: Does the Group Invariance Theorem for all linear threshold functions?

These are limitations of the linear threshold function hypothesis set (or perceptrons). The various algorithms you mention just select a particular hypothesis in different ways (PLA, logistic regression, SVM). To be able to solve this problems, one has to move beyond linear threshold functions to nonlinear threshold functions. The nonlinear SVM can accomplish this, the neural network can accomplish this, etc.

Originally Posted by antics View Post
Late in the 60's Papert and Minsky wrote a very famous book called Perceptrons, in which they proved the Group Invariance Theorem, which shows that if the pointset is closed over the action of a mathematical group, then the output of a linear threshold classification with a weight vector learned from the perceptron algorithm will be invariant under the same group action if and only if the weights can be chosen to preserve the group.

This was historically devastating because it meant that you couldn't do things like learn to recognize whether there is an odd number of pixels turned on in an image, unless one of your features depended on all the points in your pointset. So this is a limitation of the Perceptron learning algorithm (as opposed to, say, feature selection).

One way to get around this is to use neural networks, which are capable of doing these sorts of things.

My question is this: is it known whether something similar hold for SVMs or logistic regression? Is this a limitation of any possible way to learn a linear threshold function, or can we get around it in some clever way?

I apologize if this is covered later in the couse; I haven't seen all the videos yet.
Have faith in probability
Reply With Quote