是否有成功学习奇偶校验函数的机器学习算法？

parity function是来自n位矢量的函数，如果和是奇数，则输出1，否则输出0。这可以看作是一个分类任务，其中n个输入是特征。是否有成功学习奇偶校验函数的机器学习算法？

有什么机器学习算法可以学习这个功能吗？明显随机的决策森林不会成功，因为任何严格的特征子集都没有预测能力。另外，我相信没有固定深度的神经网络会成功，因为计算奇偶校验函数不在复杂类AC0中。

2012-02-28 Petter

对于固定* n *，是不是具有足够大的隐藏层的两层感知器就足够了？ – 2012-02-28 16:50:21

好吧，是的。如果在输入位的每个组合00011110101的隐藏层中都有一个节点，则它是平常可能的。然后，隐藏节点的数量将随着n成指数增长。 – Petter 2012-03-02 15:48:07

通常你应该在你的MLP中使用大约2 * n个隐藏节点和一个隐藏层，它应该可以工作。标准反向传播是一种过时的人工神经网络优化算法。我建议使用Levenberg-Marquardt，Conjugate Gradient，Quickprop或RProp。 – alfa 2012-03-03 21:24:08

高斯过程分类怎么样？您可以通过n维输入向量和1维奇偶校验位输出来训练模型。然后，对于任何测试输入，您可以要求预测。你可以查看这本在线书。
http://www.gaussianprocess.org/gpml/chapters/
第3章讲述了分类问题。

来源

2012-02-29 08:11:27 YBE

多项式SVM可以做到这一点。将零编码为1，将1编码为-1。对于n个变量（比特），您需要一个n阶多项式内核。当计算内核时，它也隐含地计算值x1 * x2 * ... * xn（其中xi是第i个输入变量）。如果结果为-1，则表示奇数个数，否则您的偶数个。

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

来源

2012-03-02 11:06:25 George

有关多项式SVMs的好处！具有一个隐藏层的神经网络平凡能够计算任何布尔函数，但是隐藏层将不得不在n中以指数规律增长。 – Petter 2012-03-02 15:41:49

我想我的错误印象是神经网络在某种程度上等同于布尔电路。 – Petter 2012-03-02 15:43:56

是否有成功学习奇偶校验函数的机器学习算法？

回答

相关问题