Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915495686438912 |
|---|---|
| author | Nicolau, Marcio Tavares, Anderson R. Zhang, Zhiwei Avelar, Pedro Flach, João M. Lamb, Luis C. Vardi, Moshe Y. |
| author_facet | Nicolau, Marcio Tavares, Anderson R. Zhang, Zhiwei Avelar, Pedro Flach, João M. Lamb, Luis C. Vardi, Moshe Y. |
| contents | 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 interpretable neurosymbolic AI methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2009_05908 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models Nicolau, Marcio Tavares, Anderson R. Zhang, Zhiwei Avelar, Pedro Flach, João M. Lamb, Luis C. Vardi, Moshe Y. Machine Learning I.2; I.2.4; I.2.6 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 interpretable neurosymbolic AI methods. |
| title | Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models |
| topic | Machine Learning I.2; I.2.4; I.2.6 |
| url | https://arxiv.org/abs/2009.05908 |