Multi-Label Classification Neural Networks with Hard Logical Constraints

Eleonora Giunchiglia, Thomas Lukasiewicz

In machine learning, classification is often treated as a series of independent predictions. However, real-world labels are frequently interconnected. For instance, a medical image containing a "stomach" must, by definition, also contain the "gastrointestinal system." Standard neural networks often struggle with this inherent logic, sometimes predicting a specific sub-category while failing to recognize the broader parent category.

Researchers at the University of Oxford have introduced a novel approach to bake these logical rules directly into neural network architectures, ensuring predictions are "coherent by construction."

The Challenge of Logical Inconsistency

The paper addresses Hierarchical Multi-Label Classification (HMC) and its generalization, Logically Constrained Multi-Label Classification (LCMC). In these settings, labels must obey specific rules, such as hierarchy: if a sample belongs to subclass $A_1$, it must also belong to superclass $A$.

Standard neural networks face two primary hurdles:

  1. Incoherency: At inference time, a vanilla model might predict a subclass with high confidence but its superclass with low confidence, a logical impossibility.
  2. Data Sparsity: Deep levels of a hierarchy often have very few training examples, making it difficult for models to learn specific categories effectively.
Standard neural networks often produce logically inconsistent decision boundaries, where the predicted region for a subclass (Class $A_1$) does not align correctly with its superclass (Class $A$).

Proposed Methodology: Coherency by Construction

The researchers propose two new models, C-HMCNN(h) and CCN(h), which incorporate hard logical constraints directly into the network's architecture and loss functions.

1. The Constraint Layer

Instead of raw probabilities, the models utilize a Constraint Layer on top of a base network $h$. For hierarchies (C-HMCNN), this layer ensures the probability of a parent class is at least the maximum probability of any of its children. For general logic (CCN), they use stratified negation to handle complex "if-then" rules.

2. Max Constraint Loss (CLoss)

A novel loss function, CLoss, teaches the network to exploit these constraints during training. If the model is confident about a child class, CLoss forces it to be equally confident about the parent class, effectively propagating supervision through the logical rules.

The proposed C-HMCNN(h) and constrained variants ($f^+, g^+$) ensure that decision boundaries are logically consistent, with subclasses properly nested within superclasses.

3. Efficient Implementation

To handle complex logic without circular dependencies, the authors use stratification to break rules into sequential layers (strata). This is implemented using vectorized operations, allowing logical checks to run efficiently on GPUs.

Experimental Results and Insights

The models were evaluated across 20 HMC benchmarks (genomics, medical imaging, text) and 16 new LCMC datasets.

  • State-of-the-Art Performance: CCN(h) achieved top performance on 17 out of 20 HMC datasets, significantly outperforming previous models.
  • Logic as Supervision: The key insight is that constraints act as background knowledge. By enforcing hierarchy, the model uses abundant superclass data to improve predictions for rare subclasses.
  • Robustness: In synthetic tests with complex class boundaries, CCN(h) remained stable by relying on its logical "guardrails," whereas standard models' performance declined.

Conclusion

By integrating hard logical constraints into the learning process, the researchers have moved beyond simple post-processing. Their approach not only prevents illogical mistakes but leverages logical structure to improve learning from imbalanced data. Future work may extend these "hard" constraints to "soft" rules for less rigid relationships or apply these layers to regression tasks.

Summary updated

Abstract

Multi-label classification (MC) is a standard machine learning problem in which a data point can be associated with a set of classes. A more challenging scenario is given by hierarchical multi-label classification (HMC) problems, in which every prediction must satisfy a given set of hard constraints expressing subclass relationships between classes. In this article, we propose C-HMCNN(h), a novel approach for solving HMC problems, which, given a network h for the underlying MC problem, exploits the hierarchy information in order to produce predictions coherent with the constraints and to improve performance. Furthermore, we extend the logic used to express HMC constraints in order to be able to specify more complex relations among the classes and propose a new model CCN(h), which extends C-HMCNN(h) and is again able to satisfy and exploit the constraints to improve performance. We conduct an extensive experimental analysis showing the superior performance of both C-HMCNN(h) and CCN(h) when compared to state-of-the-art models in both the HMC and the general MC setting with hard logical constraints.
BibTeX
@article{giunchiglia2021multi,
  author = {Eleonora Giunchiglia and Thomas Lukasiewicz},
  title = {{Multi-Label Classification Neural Networks with Hard Logical Constraints}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  doi = {10.1613/jair.1.12850},
}
Figure