Structured Prediction

The defining feature of structured prediction is that individual output elements are interdependent. The correct label for one element depends on the labels assigned to others. This requires models to consider the joint probability of the entire output structure, not just independent classifications.

• Example: In part-of-speech tagging, labeling a word as a verb is more likely if the preceding word is a noun.
• Contrast: In simple multi-class classification, each prediction is made independently of others.

The set of all possible valid output structures is exponentially large relative to the input size. For a sequence of length N with K possible labels per position, there are K^N possible sequences. This makes exhaustive search impossible, necessitating efficient inference algorithms like the Viterbi algorithm for Hidden Markov Models or beam search for neural sequence models.

• Challenge: The model must search this vast space to find the most probable structure.
• Solution: Leverage the structure of the problem (e.g., Markov assumptions, graph connectivity) to perform dynamic programming.

Training requires specialized structured loss functions that measure the discrepancy between a predicted structure and the ground truth. Unlike standard loss functions (e.g., cross-entropy for a single label), these must account for the entire output's correctness.

• Hamming Loss: Counts the number of incorrectly labeled individual elements.
• Structured Hinge Loss: Used in Structured Support Vector Machines (SSVMs), it penalizes predictions based on the difference between the score of the correct structure and the highest-scoring incorrect structure.
• Conditional Random Fields (CRFs) use a log-likelihood objective that directly models the probability of the correct sequence.

Specific model families are designed to capture output dependencies.

• Graphical Models: Hidden Markov Models (HMMs) for sequences and Conditional Random Fields (CRFs) are foundational probabilistic models that explicitly define dependencies via a graph structure.
• Structured Perceptron/SVMs: Discriminative models that learn a linear function for scoring entire structures.
• Neural Sequence Models: Modern approaches use Recurrent Neural Networks (RNNs), Transformers, or Graph Neural Networks (GNNs) as powerful feature extractors, often combined with a CRF layer on top for structured output (e.g., BiLSTM-CRF for named entity recognition).

The process separates into two distinct computational challenges:

• Learning: Estimating model parameters from training data. For models like CRFs, this often involves optimizing the conditional log-likelihood, which requires performing inference (calculating partition functions and marginal distributions) during each training step.
• Inference (Decoding): Given a trained model and a new input, finding the highest-scoring output structure: y* = argmax_y score(x, y). This is typically solved with algorithms like Viterbi decoding (for linear chains) or max-product belief propagation (for general graphs).

Structured prediction is fundamental to numerous AI tasks where the output has inherent composition.

• Natural Language Processing: Named Entity Recognition (output: spans and types), Dependency Parsing (output: tree of grammatical relations), Machine Translation (output: sequence in another language).
• Computer Vision: Image Segmentation (output: label per pixel), Human Pose Estimation (output: graph of keypoints).
• Bioinformatics: Protein Secondary Structure Prediction (output: sequence of structural labels).
• LLM Context Engineering: Enforcing JSON Schema output is a form of structured prediction where the model must generate tokens that collectively form a valid, specific data structure.

Named Entity Recognition (NER) is the task of identifying and classifying specific entities mentioned in unstructured text into predefined categories. The output is a structured list or sequence of tagged spans.

• Key Entities: People (PER), Organizations (ORG), Locations (LOC), Dates, Monetary values.
• Output Structure: Typically a sequence of [entity, type, start_index, end_index] tuples or a BIO-tagged sequence (e.g., B-PER, I-PER, O).
• Example: From "Apple was founded by Steve Jobs in Cupertino," a model extracts [["Apple", "ORG", 0, 5], ["Steve Jobs", "PER", 22, 32], ["Cupertino", "LOC", 36, 45]].
• Use Case: Information extraction for search engines, populating knowledge graphs, and preprocessing for question-answering systems.

This task involves analyzing the grammatical structure of a sentence to produce a parse tree that reveals syntactic dependencies or semantic roles. The output is a hierarchical tree structure.

• Syntactic Parsing: Produces a constituency or dependency parse tree. For example, a dependency parse links words via relations like nsubj (nominal subject) or dobj (direct object).
• Semantic Parsing: Maps natural language to a formal meaning representation, such as Abstract Meaning Representation (AMR) or a logical form executable by a database (e.g., SQL).
• Output Structure: A rooted tree where nodes are words/phrases and edges are labeled relationships.
• Use Case: Grammar checking, machine translation, and enabling natural language interfaces to databases.

Image segmentation partitions a digital image into multiple segments (pixel groups) to simplify its representation. The output is a pixel-wise mask, a structured grid matching the input dimensions.

• Instance Segmentation: Identifies and delineates each distinct object of interest, assigning a unique label to each instance.
• Semantic Segmentation: Classifies each pixel into a general category (e.g., road, car, pedestrian) without distinguishing between instances.
• Output Structure: A 2D array or tensor where each cell (pixel) contains a class label or instance ID.
• Use Case: Autonomous vehicle perception, medical image analysis (tumor detection), and photo editing software.

While often producing plain text, machine translation is a core structured prediction task where the model must generate a sequence in a target language that preserves the meaning and grammatical structure of the source sequence.

• Interdependence: Each generated word depends on the source context and previously generated target words, requiring the model to maintain complex structural alignment.
• Output Structure: A sequence of tokens in the target language vocabulary, often with an associated alignment matrix.
• Advanced Forms: Includes simultaneous translation (outputting tokens before the input is complete) and multilingual translation with a single model.
• Use Case: Real-time translation services, cross-lingual information retrieval, and localization of content.

Part-of-Speech (POS) tagging assigns a grammatical tag (e.g., noun, verb, adjective) to each word in a sentence. The output is a sequence of tags aligned with the input token sequence.

• Tag Sets: Uses standardized sets like the Penn Treebank tagset (e.g., NN for singular noun, VBZ for verb, 3rd person singular present).
• Structural Constraint: Tags are interdependent; the tag for a word is influenced by its neighbors (e.g., a determiner is likely followed by a noun or adjective).
• Output Structure: A one-to-one mapping: [("The", "DT"), ("quick", "JJ"), ("brown", "JJ"), ("fox", "NN"), ...].
• Use Case: A foundational preprocessing step for parsers, text-to-speech systems, and grammar tools.

This task involves converting unstructured or semi-structured text (like resumes, invoices, or research papers) into a rigorously defined, nested data schema such as JSON or XML.

• Schema-Driven: The output must conform to a predefined JSON Schema specifying required fields, data types, and nested object structures.
• Complex Interdependencies: Extracted fields often relate to each other (e.g., an employment history array where each entry has start_date, end_date, and title fields).
• Output Structure: A complex, validated JSON object, often involving arrays of objects, optional fields, and specific value formats (ISO dates, normalized currencies).
• Use Case: Automated document processing, populating CRM/ERP systems, and generating training data for knowledge graphs.

A technique for guaranteeing that a large language model's output strictly adheres to a predefined JSON Schema. This goes beyond simple JSON syntax to enforce data types, required fields, value constraints, and nested structures. It is a critical method for creating reliable data contracts between an LLM and downstream applications.

• Implementation: Often involves providing the schema within the system prompt and using model features like OpenAI's response_format or libraries like Outlines or Guidance for constrained decoding.
• Use Case: Ensuring an API response always contains a user_id as a string and a score as a number between 0 and 1.

A constrained decoding technique that restricts a language model's token-by-token generation to follow a formal grammar. The grammar, often defined in Extended Backus-Naur Form (EBNF), acts as a rule set that the model's output must satisfy, ensuring syntactically valid output in formats like JSON, SQL, or custom DSLs.

• Mechanism: The decoder uses the grammar to filter the model's vocabulary at each generation step, allowing only tokens that can lead to a complete, valid parse tree.
• Advantage: Provides stronger guarantees than prompting alone, virtually eliminating syntax errors in the generated output.

The specific task of using a language model to identify and pull specific entities, relationships, or facts from unstructured text and output them in a structured schema. This is a prime application of structured prediction where the input is free-form prose and the output is a normalized database record or API object.

• Process: Involves a prompt that defines the target schema (e.g., extract person_name, company, date from a news article) and often uses few-shot examples.
• Output: A JSON object where each field corresponds to a piece of information extracted from the source text.

The automated pipeline steps that occur after a model generates a raw response. Output Validation checks the response against a schema or set of business rules for syntactic and semantic correctness. Output Post-Processing then transforms the valid output into a canonical format.

• Validation Tools: Libraries like Pydantic or jsonschema are used to validate structure and data types.
• Post-Processing Actions: Can include normalization (dates to ISO 8601), sanitization (escaping HTML), and parsing (converting a JSON string to a native object).

The use of prompt engineering, constrained decoding, or post-processing to mold a model's free-form output into a desired structured or stylistic form. It is the overarching practice that encompasses many specific techniques for controlling output.

• Methods:
  • Instructional Shaping: "You are a helpful API. Respond only in JSON."
  • Example Shaping: Providing a clear output template in a few-shot prompt.
  • Algorithmic Shaping: Using grammar-based decoding to restrict token choices.
• Goal: To create predictable, integrable outputs from inherently stochastic models.

An advanced inference-time algorithm where the language model's token generation is dynamically influenced by a live, stateful representation of the output schema. This is a more integrated approach than simple grammar filtering, as the decoding process is actively guided by the schema's requirements.

• How it Works: The decoder maintains the current state of the partially generated object (e.g., "inside a required address object") and uses this context to bias the model's logits towards tokens that fulfill the schema's next expected element.
• Benefit: Can improve efficiency and coherence compared to post-hoc validation, as invalid paths are avoided during generation.