Enforcing Global Structural Constraints on Local Classifiers

181 concepts142 papers1 proposal

When building machine learning models for structured natural language tasks—such as parsing sentences, extracting opinions, or identifying semantic roles—it is tempting to break the problem down into small, manageable pieces. We train a classifier to look at a specific phrase and predict whether it is a noun group, or look at a word and decide if it represents the subject of a verb. These are local classifiers. They are highly optimized, computationally efficient, and excellent at capturing immediate context.

However, language does not operate in a vacuum of isolated tokens; it obeys strict global rules. For example, in a single clause, a verb cannot typically have two separate phrases acting as its unique subject. In shallow parsing, phrases cannot physically overlap or intersect.

When local classifiers make independent predictions across a sequence, they suffer from a fundamental blindness: they cannot see what their neighbors are doing. As a result, a set of locally optimal predictions often aggregates into a globally impossible output. As noted by Dan Roth et al. in Shallow Parsing by Inferencing with Classifiers, local machine learning models lack an inherent mechanism to adjudicate between competing candidates, frequently generating mutually exclusive predictions like overlapping phrase boundaries.

The Tension Between Local Optimization and Global Validity

This core challenge creates what Vasin Punyakanok describes in Learning and Inference over Constrained Output as a fundamental tension between optimizing for individual component accuracy and ensuring the entire output set adheres to global consistency rules.

This structural inconsistency manifests across various domains:

Adjudication via Global Inference Layers

To resolve these conflicts, researchers introduced an elegant paradigm shift: keep the local classifiers, but overlay a global inference layer that acts as an adjudicator. Instead of accepting the raw, independent choices of each classifier, the system treats local outputs as "votes" or "scores" and finds the combination of labels that maximizes the total score while strictly obeying global constraints.

Before exact optimization frameworks became widespread, early approaches relied on heuristic post-processing to resolve conflicts. For instance, Richard Johansson in Dependency-based Semantic Role Labeling of PropBank utilized a post-processing stage to evaluate candidate semantic structures against global constraints, ensuring a predicate does not assign the same semantic role to multiple arguments.

However, to guarantee mathematical and logical consistency, researchers turned to two primary exact optimization frameworks:

1. Integer Linear Programming (ILP)

In the ILP framework, the local classifier outputs are converted into weights for an objective function. The structural and linguistic rules are then formalized as linear constraints (e.g., $x_A + x_B \le 1$ to prevent overlapping spans $A$ and $B$). An optimization solver then searches the space of possible outputs to find the globally optimal, valid configuration.

Dan Roth et al. pioneered this in Semantic Role Labeling Via Integer Linear Programming Inference, proving that enforcing global coherence via ILP significantly improves predicate-argument structures without requiring a full syntactic parse. Similarly, P. Koomen et al. used ILP in Generalized Inference with Multiple Semantic Role Labeling Systems to combine predictions from entirely different parsing systems into a single, structurally sound output.

2. Markov Logic Networks (MLNs)

Where ILP uses hard linear constraints, Markov Logic Networks combine the formal structure of first-order logic with probabilistic graphical models, allowing for both hard and soft global constraints. Iván V. Meza-Ruíz et al. applied this in Multilingual Semantic Role Labelling with Markov Logic, demonstrating that modeling dependencies between all components simultaneously prevents independent classifiers from violating task-specific rules.

Joint Inference and Multi-Predicate Coordination

The necessity of global constraints becomes even clearer when moving from single relations to sentence-wide or document-wide structures. In sentences with multiple verbs, predicates often share arguments. If each predicate is analyzed in isolation, the system may assign semantically incompatible roles to the same token across different actions.

Haitong Yang addresses this directly in Multi-Predicate Semantic Role Labeling, introducing a joint modeling approach that allows multiple predicates to coordinate their argument assignments. By moving away from isolated pipelines toward unified information networks—such as those proposed by Heng Ji et al. in Constructing Information Networks Using One Single Model—models can enforce type-based constraints across entities, relations, and events simultaneously, drastically mitigating error propagation.

Why Global Constraints Matter in the Era of Deep Learning

With the advent of deep contextual embeddings and architectures like Transformers, one might assume that local classifiers can implicitly learn these global constraints from data. However, empirical evidence shows that even deep neural networks struggle to guarantee structural well-formedness in their raw outputs.

Modern architectures excel at semantic representation but still lack explicit mechanisms to enforce hard structural constraints in the output label space. For example, Qingrong Xia et al. in Semantic Role Labeling as Dependency Parsing: Exploring Latent Tree Structures inside Arguments demonstrate that syntax-agnostic neural models frequently produce fragmented outputs that violate basic linguistic principles unless paired with a span-constrained TreeCRF decoder. Similarly, Sida Gao et al. show in Training for Gibbs Sampling on Conditional Random Fields with Neural Scoring Factors that explicitly modeling long-range dependencies in the label space provides significant value over pure neural scoring.

By separating the representation of local features from the enforcement of global structural rules, this framework ensures that machine learning models remain both statistically powerful and logically consistent.

Key Foundational Work

Shallow Parsing by Inferencing with Classifiers (2000) — contributed 4 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 139 papers
  2. Version 1 · 2026-10-04 · 135 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_global_structural_constraints_6ccfd6a8,
  title = {global structural constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-structural-constraints/rdr_6ccfd6a8c24a4d64b0d0cdf09dbff47f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_global_structural_constraints_6ccfd6a8_v2,
  title = {global structural constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-structural-constraints/rdr_6ccfd6a8c24a4d64b0d0cdf09dbff47f/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake