Is there a machine learning algorithm which successfully learns the parity function?

Question

The parity function is a function from a vector of n bits and outputs 1 if the sum is odd and 0 otherwise. This can be viewed as a classification task, where the n input are the features.

Is there any machine learning algorithm which would be able to learn this function? Clearly random decision forests would not succeed, since any strict subset of features has no predictive power. Also, I believe no neural network of a fixed depth would succeed, since computing the parity function is not in the complexity class AC0.

Answer 1

Polynomial SVMs can do this. Encode zeros as 1 and ones as -1. For n variables (bits), you need a polynomial kernel of degree n. When the kernel is computed, it also implicitly computes the value x1 * x2 * ... * xn (where xi is the i-th input variable). If the result is -1, you have an odd number of ones, otherwise you have an even number of ones.

If I'm not mistaken, Neural Networks should also be able to compute it. As far as I remember, Neural Networks with 2 hidden layers and sigmoid units are able to learn any arbitrary function.