A Learnability Analysis on Neuro-Symbolic Learning
This provides a principled framework for determining learnability in neuro-symbolic learning, which is incremental as it builds on existing hybrid systems analysis.
This paper tackles the problem of analyzing the learnability of neuro-symbolic tasks by characterizing them through derived constraint satisfaction problems, showing that tasks are learnable only if these problems have unique solutions, and establishing error bounds based on hypothesis space clustering and asymptotic error scaling with solution disagreement.
This paper analyzes the learnability of neuro-symbolic (NeSy) tasks within hybrid systems. We show that the learnability of NeSy tasks can be characterized by their derived constraint satisfaction problems (DCSPs). Specifically, a task is learnable if the corresponding DCSP has a unique solution; otherwise, it is unlearnable. For learnable tasks, we establish error bounds by exploiting the clustering property of the hypothesis space. Additionally, we analyze the asymptotic error for general NeSy tasks, showing that the expected error scales with the disagreement among solutions. Our results offer a principled approach to determining learnability and provide insights into the design of new algorithms.