Verification Learning: Make Unsupervised Neuro-Symbolic System Feasible
This addresses the challenge of over-reliance on labeled data in neuro-symbolic systems, making them more feasible for unsupervised tasks, though it is incremental in improving existing paradigms.
The paper tackles the problem of unsupervised neuro-symbolic learning by introducing Verification Learning, which replaces label-based reasoning with a verification process using unlabeled data and rules, achieving significant performance and efficiency improvements in tasks like addition, sorting, matching, and chess.
The current Neuro-Symbolic (NeSy) Learning paradigm suffers from an over-reliance on labeled data, so if we completely disregard labels, it leads to less symbol information, a larger solution space, and more shortcuts-issues that current Nesy systems cannot resolve. This paper introduces a novel learning paradigm, Verification Learning (VL), which addresses this challenge by transforming the label-based reasoning process in Nesy into a label-free verification process. VL achieves excellent learning results solely by relying on unlabeled data and a function that verifies whether the current predictions conform to the rules. We formalize this problem as a Constraint Optimization Problem (COP) and propose a Dynamic Combinatorial Sorting (DCS) algorithm that accelerates the solution by reducing verification attempts, effectively lowering computational costs and introduce a prior alignment method to address potential shortcuts. Our theoretical analysis points out which tasks in Nesy systems can be completed without labels and explains why rules can replace infinite labels for some tasks, while for others the rules have no effect. We validate the proposed framework through several fully unsupervised tasks including addition, sort, match, and chess, each showing significant performance and efficiency improvements.