是否有可以成功学习奇偶函数的机器学习算法? [英] Is there a machine learning algorithm which successfully learns the parity function?

问题描述

奇偶校验功能是n位向量的函数，如果总和输出1为奇数，否则为0.可以将其视为分类任务，其中n个输入为要素.

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.

是否有任何机器学习算法可以学习此功能?显然，随机决策森林不会成功，因为任何严格的特征子集都没有预测能力.另外，我认为固定深度的神经网络不会成功，因为计算奇偶校验功能不在复杂度类中 AC0 .

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.

推荐答案

多项式SVM可以做到这一点. 将0编码为1，将1编码为-1. 对于n个变量(位)，您需要一个阶数为n的多项式内核. 计算内核时，它还隐式计算值x1 * x2 * ... * xn(其中xi是第i个输入变量). 如果结果为-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.

如果我没记错的话，神经网络也应该能够计算它.据我所知，具有2个隐藏层和S型单元的神经网络能够学习任何任意函数.

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.

这篇关于是否有可以成功学习奇偶函数的机器学习算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！