是否有成功學習奇偶校驗函數的機器學習算法？

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

是否有成功學習奇偶校驗函數的機器學習算法？

回答

相關問題