machine-learning - 是否有一种机器学习算法可以成功学习奇偶校验函数？

Question

parity function是 n 位向量的函数，如果总和为奇数则输出 1，否则输出 0。这可以看作是一个分类任务，其中 n 个输入是特征。

是否有任何机器学习算法能够学习这个函数？显然随机决策森林不会成功，因为任何严格的特征子集都没有预测能力。另外，我相信固定深度的神经网络不会成功，因为计算奇偶校验函数不属于复杂性类别 AC0 .

Answer 1

多项式 SVM 可以做到这一点。将 0 编码为 1，将 1 编码为 -1。对于 n 个变量(位)，您需要一个 n 次多项式核。当计算内核时，它还会隐式计算值 x1 * x2 * ... * xn(其中 xi 是第 i 个输入变量)。如果结果是 -1，则有奇数个，否则有偶数个。

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