Verification Learning: Make Unsupervised Neuro-Symbolic System Feasible

Dear Reviewer W1W6:

Thank you for valuable comments.

Regarding Question 1 and Weaknesses 1:

Methodological Innovations:

1. Explored fully unsupervised Nesy algorithms and provided a systematic solution.
2. Proposed a universal approach for finding globally optimal solutions to Nesy search problems solvable in sub-exponential time.
3. Demonstrated that in the Nesy domain, a single validation function can replace an entire complex knowledge base.
4. Shifted the paradigm from inference to validation, expanding the symbolic space complexity that can be solved.

Theoretical Innovations:

1. Proved that when a symbolic system is sufficiently differentiated, rules can theoretically replace all labels. This is equivalent to proving that rule-based clustering alone can achieve classification.
2. Demonstrated that monotonicity is a necessary and sufficient condition Nesy to achieve a globally optimal solution in sub-exponential time.
3. Established that the irreplaceability of symbols within a system is a necessary condition for their correct recognition.

Regarding Question 2:

Regarding Formula (1): In Formula (1), we have generalized various algorithms, such as deepproblog and others, to highlight the commonality in their form. Therefore, the Score does not refer to any specific score. I outline the differences in the Score chosen by different algorithms for comparison.

• In deepproblog and deepstochlog, $Score(S)=\prod_{i=1}^{|path|} p(path_i)$ where path refers to the path leading to S derived from the root.
• In ABL, $Score(S)=\sum_{i=1}^{m}[f(x_i)==s_i]$ known as the Consistency, which represents the number of symbols in S that align with the predictions.
• In WSABL, $Score(S)=\prod_{i=1}^{m} confidence(x_i)_{s_i}$ known as the Confidence, which represents the probability that predicts.
• In VL. In the independent mode, we use the Confidence. In the non-independent mode, Score(S)=(Consistency(S), Confidence(S)). This means seeking the solution with the highest consistency and, the one with the highest confidence among them.

Regarding Proofs

For Theorem 4.1, we use proof by contradiction. Suppose for the i-th largest solution i>1, there is no 0<j<i such that i=suc(j). Then, there must exist some l where i=suc(l) and score(l)>score(i). Since no 0<j<i satisfies i=suc(j), it follows that l>i, contradicting score(l) >score(i). Thus for any i>1, there must exist 0<j< i such that i=suc(j).

The proof for Theorem 4.2 follows the same reasoning as Theorem 4.1.

For Proposition 4.3, if S is independent in terms of Score, then Score(S) is the product of individual scores. This ensures that reordering any subset does not affect the relative ranking of scores, making independence a sufficient condition for monotonicity.

For Theorem 6.1, let $\hat{R}(f)$ be the empirical loss of the best permutation for clustering. The difference between its empirical and generalization error is bounded by $2\rho \mathcal{R}_n(F)+3 \sqrt{\frac{\log(2/\delta)}{2n}}$.

The difference between the optimal and true permutation is given by $R^{up}_{task}$.

Regarding Weaknesses 2 and Question 3:

We expanded the experiments by adding 4 new comparison methods. These include 2 classic methods, Hybrid and ABL-zoopt, where Hybrid is an algorithm for solving the CSP problems using neural networks, and ABL-zoopt is a classic method based on gradient-free optimization. Additionally, we included 2 recent methods, REFL and PSP. REFL accelerates the inference process using the Reflection mechanism which is the best paper at AAAI 25. PSP is the latest algorithm that combines probabilistic symbolic perception with symbolic context.

Additionally, we have included more evaluation metrics. In addition to the accuracy in symbol recognition, we have also included classic metrics such as Recall, Precision, F1 Score, and ROC-AUC. Furthermore, we have added the Global Accuracy metric, which describes the probability that the network provides the correct answer for all symbols in a given set. It is used to reflect the algorithm's ability to find the precise solution.

Dear Reviewer Vjyz:

Thank you for valuable comments.

Regarding the Benefits of Sorting Algorithms

We supplement this comparison with the time consumption of the naïve sorting method. As the space grows exponentially, the time required by the naïve method increases tenfold, while DCS remains stable.

Regarding Monotonicity

When monotonicity is not satisfied, it can be proven that no algorithm with a complexity lower than exponential can find the optimal solution. Fortunately, the optimization objectives in current Nesy frameworks almost satisfy monotonicity.

1.Metrics that satisfy independence An example is the Confidence Score, defined as: $Confidence(S)=\prod_{i=1}^{m} confidence(x_i)_{s_i}$

2.Metrics that do not satisfy independence but still satisfy monotonicity. $Consistency(S)=\sum_{i=1}^{m}\left[ f(x_i)=s_i\right]$

3.Combinations of Metrics Any metric formed by adding, multiplying (with positive values), or concatenating also retains monotonicity. For example, the two-dimensional tuple: $(Consistency(S), Confidence(S))$ remains a monotonicity-preserving metric.

Regarding Practical Applications

In applications, VL can be applied in various scenarios. In autonomous driving, a vehicle can automatically recognize pedestrians, traffic lights, and crosswalks in an image using only the traffic rules. In circuit fault analysis, VL can identify faulty components based solely on input circuit diagrams and electrical rules. We further validated VL in real-world scenarios by conducting experiments on the Road-R autonomous driving dataset with driving rules.

Regarding Ablation Study on Alignment

Without distribution alignment, unsupervised learning can effectively cluster similar samples together but struggles to associate them with the correct symbols.

Regarding Experimental Designs or Analyses

The goal of this work is to train neural networks without any labels by utilizing verification functions. This enables the neural networks to accurately extract symbols from raw data. All accuracy values reported in this paper correspond to the accuracy of the neural network in symbol recognition. In Section 7, we introduce the general experimental setup. A LeNet backbone was employed in all cases, with training conducted for 10 epochs.

Regarding Question 1

In this paper, all the permutations we describe are global permutations applied to the entire symbol system. The permutation we aim to express is holistic (in a 9x9 grid) and refers to symbol permutations on the entire Sudoku board. For example, by permuting all the 1s in the 9x9 grid to 2s, 2s to 3s, ..., and 9s to 1s, this global permutation will cause corresponding changes in each row, column, and 3x3 grid, but will not violate any of the constraints on any of them. For example, in a vision Sudoku task with 81 unlabeled images, a completely unsupervised approach would fail to prevent the images from being interpreted as permuted labels. Due to the possibility of all labels being permuted, the error bound caused by the Sudoku task itself can reach 100%.

Regarding Question 2

In Nesy, machine learning models such as neural networks play a role in recognizing abstract symbols from raw data. Our work is no different in this regard, and our ultimate goal is to complete the neural network training process using only a verification function as the knowledge base. The pipeline described in this paper can be summarized as follows:

1. A set of samples $X=[x_1,\dots,x_m]$ is input into the network f.
2. The neural network outputs probability predictions for this set of samples g(X) and label predictions f(X).
3. The probability predictions g(X) are then adjusted through distribution alignment to obtain $g_{align}(X)$.
4. A Score is chosen as an optimization goal with monotonicity.
5. The DCS is called to obtain the optimal result $Y^{val}$ validated by the verification function.
6. The result $Y^{val}$ is used as supervision information, and the loss is computed by comparing it with g(X).

Dear reviewer NuWZ:

Thank you for valuable comments.

Regarding Weakness 1:
About the language, you are absolutely correct. "KL" should be corrected to "VL"; this was a typographical error. Thank you for pointing it out.
About the formulas, we have provided more detailed explanations for all of them. If anything remains unclear, please feel free to point it out:

• Equations (1) and (2) summarize the training methods of previous label-based neuro-symbolic learning algorithms. Equation (1) generalizes the training method of algorithms like DeepProbLog, which utilize all candidate solutions for training. Equation (2) generalizes the training method of algorithms like ABL, which select the highest-scoring candidate solution from the search results for training.
• Equation (3) describes the process of aligning the predicted probabilities from the neural network with the prior distribution of symbols, which helps prevent the network's predictions from collapsing into trivial solutions. For example, the addition rule is still satisfied even when the neural network predicts all symbols as 0.
• Equations (4) and (5) describe the upper bound and mean error caused by the task itself in unsupervised neuro-symbolic systems. Equation (4) states that the error upper bound is equal to the sum of the distributions of all non-fixed-point symbols in the symbolic system, where a fixed point refers to symbols whose functions cannot be replaced in the system. Equation (5) states that the mean error is equal to the sum of the ratios between the distribution of each symbol and the number of its orbits, where the number of orbits represents how many other symbols can replace the function of a given symbol.
• Equation (6) describes the empirical error caused by training a neural network in an unsupervised manner. Since the training error in unsupervised learning should be determined by its clustering error, the minimum error under all label assignments should be considered.
• Equation (7) describes the upper-bound generalization error of an unsupervised neuro-symbolic system. This error is jointly determined by the training error, the complexity of the model space, and the task-specific error upper bound.

Regarding Weakness 2:
The observed performance variation is due to the early termination of the neural network training process before full convergence. To ensure an objective comparison, we maintained consistent hyperparameters across all methods and experimental settings. Specifically, we fixed the number of training epochs for all algorithms to 10 across different bases.
In the particular setting you pointed out, while the accuracy was 51.40% at the 10th epoch, it exceeded 90% by the 13th epoch:

This indicates that the algorithm did not fail; rather, due to the expanded symbolic space, the neural network requires more training. We did not adopt a higher number of epochs because this would cause DeepProbLog and NeurASP to exceed the time limit (300 hours).

Regarding Weakness 3:
In Section 3 of the original paper, we analyzed why methods such as DeepProbLog and NeurASP fail when reasoning without label Y, and why the VL paradigm remains effective even without relying on Y. Here, we further expand this analysis by incorporating specific tasks.
The fundamental reason why DeepProbLog, NeurASP and etc. fail in unsupervised tasks is that they lack the ability to precisely identify the correct symbolic label S from a vast set of candidate symbolic labels candidates(S).

• In supervised tasks, |candidates(S)| is relatively small, making this issue less severe.
• In unsupervised tasks, |candidates(S)| is significantly larger, amplifying the problem and ultimately leading to algorithm failure.

For example, in an addition task:

• With supervision, the KB consists of addition rules. Given an equation like Image1+Image2=Y, when Y=0, we get candidates(S) = {(0,0)}; when Y=1, candidates(S) = {(0,1), (1,0)}, and so on. The average of |candidates(S)| is only 4.91, indicating a relatively low level of imprecision.
• Without supervision, where no Y is provided, given Image1+Image2=Image3 Image4, the KB alone must infer: candidates(S)={(0,0,0,0),...,(9,9,1,8)}. Here, |candidates(S)| reaches 100, making it infeasible for DeepProbLog and NeurASP to identify the correct symbolic label S efficiently. The overwhelming number of imprecise labels leads to training failure.

In contrast, VL has a significant advantage in efficiently identifying the precise symbolic label S from candidates(S). VL excels even when |candidates(S)| is large because it leverages the proposed combinatorial ranking algorithm, which efficiently and precisely selects the optimal symbolic label S that adheres to the rules.

Dear reviewer 3PLJ:

Thank you for valuable comments.

Weakness 1, Suggestions 1 & 2

First, we need to clarify that in Nesy, for more complex scenarios where monotonicity is not satisfied, no algorithm can find the global optimal solution in sub-exponential time. Monotonicity is both a necessary and sufficient condition for solving it.

In a Nesy problem, where there are m symbols, each with n possible values, the complexity of the solution space is $O(n^m)$. The goal is to find the optimal solution among them.

• If monotonicity holds, the DCS algorithm can solve the problem efficiently with extremely low complexity.
• If monotonicity does not hold, the only way to guarantee finding the optimal solution is by exhaustively searching the entire solution space, because even if $n^m-1$ solutions have already been evaluated, there is no way to determine whether the last remaining solution is optimal.

Example 1: Independence Holds For m = 2, n = 2 suppose:

score=[[0.4,0.6],[0.7,0.3]]

Score(s₁=v₁,s₂=v₁)=0.28
Score(s₁=v₁,s₂=v₂)=0.12
Score(s₁=v₂,s₂=v₁)=0.42
Score(s₁=v₂,s₂=v₂)=0.18

Example 2: Monotonicity Holds

Score(s₁=v₁,s₂=v₁)=0.25
Score(s₁=v₁,s₂=v₂)=0.18
Score(s₁=v₂,s₂=v₁)=0.34
Score(s₁=v₂,s₂=v₂)=0.23
monotonicity is satisfied:
Score(s₁=v₁,s₂=x)<Score(s₁=v₂,s₂=x)
Score(s₁=x,s₂=v₂)<Score(s₁=x,s₂=v₁)

Example 3: Monotonicity Does Not Hold

Score(s₁ = v₁,s₂= v₁)=0.23
Score(s₁ = v₁,s₂ = v₂)=0.25
Score(s₁ = v₂,s₂ = v₁)=0.34
Score(s₁ = v₂,s₂ = v₂)=0.18
Here, fixing one symbol’s value leads to inconsistent ranking of the other symbol’s scores, meaning monotonicity is violated. In this case, there is no alternative to brute-force enumeration to guarantee finding the optimal solution.

Weakness 2

Our theory is actually applicable. It demonstrates that in many real-world scenarios—such as traffic control, industrial anomaly detection, and circuit analysis—it is entirely feasible to replace all labels with rules for learning. Our theory also highlights that the key to replacing labels with rules lies in ensuring that different symbols within the rule system possess irreplaceability. For instance, in autonomous driving tasks, the rule "Red and green lights cannot be on simultaneously" cannot distinguish between them. However, the rule "Stop at red, go at green" effectively differentiates them. This insight is valuable for selecting meaningful rules when constructing a knowledge base.

Weakness 3 & Question 3

The primary role of distribution alignment is to initialize the neural network’s predictive distribution, preventing it from falling into trivial solutions. According to Bayes' theorem, the posterior probability learned by the model can inherently correct biased priors. When the true natural distribution is unknown, a uniform distribution can be used as the prior to ensure a sufficiently diverse initialization. This allows the model to fully utilize all available knowledge and gradually converge to the true distribution. Below is a comparison between using a uniform prior for alignment and no alignment on an imbalanced addition dataset:

Weakness 4

Our algorithm is practical as it only requires writing a verification function, significantly simplifying the complexity of knowledge compared to others. Furthermore, when dealing with a large amount of unlabeled data, writing a verification program is more cost-effective than manually labeling. VL can achieve 92.02% based on the autonomous driving rule set Road-R.

Question 1

As the size of the symbol space increases, VL exhibits a low growth in runtime. In Table 2, we compare the runtime as the number of symbol categories increases from 2 to 10, where VL's runtime only increases from 112.04 to 116.26, whereas the runtimes of DeepProbLog increase by a factor of 20. This efficiency is due to our sorting algorithm, which ensures that the first solution passing verification is the optimal one. The time complexity is O(K(logK+mlogm+nlogn)), where the constant K represents the position of the first verified solution.

Question 2

We conducted experiments to validate the robustness. In our tests, the verification function returns the correct validation result with probability p, and we gradually decrease p from 100% down to 50%(completely random). Our findings indicate that the algorithm's performance only experiences a significant decline when predictions approach complete randomness. As long as the probability of returning correct results is higher than that of returning incorrect results, VL can largely mitigate the impact of errors, demonstrating a strong fault tolerance.