Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models

Marcio Nicolau, Anderson R. Tavares, Zhiwei Zhang, Pedro H. C. Avelar, João Marcos Flach, Luis DC Lamb, Moshe Vardi
Proceedings of The 19th International Conference on Neurosymbolic Learning and Reasoning, PMLR 284:719-735, 2025.

Abstract

Computational learning theory states that many classes of boolean formulas are learnable in polynomial time. This paper addresses the understudied subject of how, in practice, such formulas can be learned by deep neural networks. Specifically, we analyze boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs with varying degrees of constrainedness. Our experiments indicate that: (i) neural learning generalizes better than pure rule-based systems and pure symbolic approach; (ii) relatively small and shallow neural networks are very good approximators of formulas associated with combinatorial optimization problems; (iii) smaller formulas seem harder to learn, possibly due to the fewer positive (satisfying) examples available; and (iv) interestingly, underconstrained 3-CNF formulas are more challenging to learn than overconstrained ones. Such findings pave the way for a better understanding, construction, and use of neurosymbolic AI methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v284-nicolau25a, title = {Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models}, author = {Nicolau, Marcio and Tavares, Anderson R. and Zhang, Zhiwei and Avelar, Pedro H. C. and Flach, Jo\~{a}o Marcos and Lamb, Luis DC and Vardi, Moshe}, booktitle = {Proceedings of The 19th International Conference on Neurosymbolic Learning and Reasoning}, pages = {719--735}, year = {2025}, editor = {H. Gilpin, Leilani and Giunchiglia, Eleonora and Hitzler, Pascal and van Krieken, Emile}, volume = {284}, series = {Proceedings of Machine Learning Research}, month = {08--10 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v284/main/assets/nicolau25a/nicolau25a.pdf}, url = {https://proceedings.mlr.press/v284/nicolau25a.html}, abstract = {Computational learning theory states that many classes of boolean formulas are learnable in polynomial time. This paper addresses the understudied subject of how, in practice, such formulas can be learned by deep neural networks. Specifically, we analyze boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs with varying degrees of constrainedness. Our experiments indicate that: (i) neural learning generalizes better than pure rule-based systems and pure symbolic approach; (ii) relatively small and shallow neural networks are very good approximators of formulas associated with combinatorial optimization problems; (iii) smaller formulas seem harder to learn, possibly due to the fewer positive (satisfying) examples available; and (iv) interestingly, underconstrained 3-CNF formulas are more challenging to learn than overconstrained ones. Such findings pave the way for a better understanding, construction, and use of neurosymbolic AI methods.} }
Endnote
%0 Conference Paper %T Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models %A Marcio Nicolau %A Anderson R. Tavares %A Zhiwei Zhang %A Pedro H. C. Avelar %A João Marcos Flach %A Luis DC Lamb %A Moshe Vardi %B Proceedings of The 19th International Conference on Neurosymbolic Learning and Reasoning %C Proceedings of Machine Learning Research %D 2025 %E Leilani H. Gilpin %E Eleonora Giunchiglia %E Pascal Hitzler %E Emile van Krieken %F pmlr-v284-nicolau25a %I PMLR %P 719--735 %U https://proceedings.mlr.press/v284/nicolau25a.html %V 284 %X Computational learning theory states that many classes of boolean formulas are learnable in polynomial time. This paper addresses the understudied subject of how, in practice, such formulas can be learned by deep neural networks. Specifically, we analyze boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs with varying degrees of constrainedness. Our experiments indicate that: (i) neural learning generalizes better than pure rule-based systems and pure symbolic approach; (ii) relatively small and shallow neural networks are very good approximators of formulas associated with combinatorial optimization problems; (iii) smaller formulas seem harder to learn, possibly due to the fewer positive (satisfying) examples available; and (iv) interestingly, underconstrained 3-CNF formulas are more challenging to learn than overconstrained ones. Such findings pave the way for a better understanding, construction, and use of neurosymbolic AI methods.
APA
Nicolau, M., Tavares, A.R., Zhang, Z., Avelar, P.H.C., Flach, J.M., Lamb, L.D. & Vardi, M.. (2025). Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models. Proceedings of The 19th International Conference on Neurosymbolic Learning and Reasoning, in Proceedings of Machine Learning Research 284:719-735 Available from https://proceedings.mlr.press/v284/nicolau25a.html.

Related Material