问题:

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.

回答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.

回答2:

What about Gaussian Process Classification? You can train your model by n-dimensional input vector and 1-dimensional parity bit output. Then for any test input you can ask for a prediction. You can check this online book.
http://www.gaussianprocess.org/gpml/chapters/
Chapter 3 addresses the classification problem.