Structured Output Prediction

From Labels to Ordered Outputs

Many prediction tasks assign a label to one instance at a time. A ranking task asks a different question: given several instances, how should they be arranged according to relevance? The output is therefore not merely a collection of independent predictions. It is an ordered list, and the position of each instance matters.

Tracing Scores into a Ranking

Let x̄ = (x1, ..., xr) be a sequence of r instances. A ranking hypothesis, written as h, receives this sequence and produces a permutation of the positions 1 through r. The instances themselves are not replaced; the hypothesis specifies the order in which their original positions should be read.

A convenient representation of the output is a score vector y with one score for each instance. To obtain the permutation π(y), sort the elements of y and track the original position of each element. The permutation therefore records positions from the original sequence, not new instance identities.

Permutation Positions

The notation π(y)i can be described as the position of yi in the sorted vector. The same ordering can therefore be discussed in two equivalent ways: list the original positions in sorted order, or assign each original element the position it occupies after sorting. In both views, the essential operation is sorting the values and using that result to describe the order of the instances.

• Treating the permutation entries as scores.

  The entries identify original positions. The scores were used to create the ordering, but the permutation records which original position appears at each sorted position.

  Fix: Keep two objects separate: y contains scores, while π(y) contains original positions arranged according to those scores.

• Ignoring the sorting direction.

  Ascending sorting places the smallest score first. The interpretation of relevance depends on the convention for the scores.

  Fix: State whether the task reads the sorted result from smallest to largest or from largest to smallest.

Three Components of Structured Prediction

Structured output prediction combines three connected choices: a linear predictor, a task-specific loss function, and a class-sensitive feature mapping. The predictor produces a structured output, the loss describes how the prediction should be evaluated against the correct output, and the feature mapping represents the relationship between the input, the candidate output, and the task's classes.

The loss and feature mapping solve different problems. The loss must be reasonable for the task: it states what counts as an undesirable structured prediction. The mapping Ψ must be class-sensitive and expressive enough to represent distinctions that matter for the task. A learning algorithm cannot compensate for definitions that fail to express the task well.

Linear Predictors and Feature Design

A linear predictor is the predictive component used in the structured-output setup. It operates together with the task-specific feature mapping Ψ so that candidate structured outputs can be represented and compared. The important design question is not only which linear learning procedure to use, but also whether Ψ captures the distinctions required by the task.

The feature mapping affects approximation error because an unsuitable representation may fail to express important task distinctions. At the same time, making the mapping more expressive is not automatically better: keeping the norm of the range of Ψ under control helps address overfitting. Good design balances sufficient task sensitivity with a controlled range.

Learning with SGD

SGD can be used to learn the linear predictor after the feature mapping Ψ and loss function Δ have been defined. This order matters. First, the task needs a representation that captures relevant structure and a loss that evaluates predictions appropriately. SGD then provides a learning procedure for the linear predictor within that design.

Efficient Structured Definitions

The definitions of Ψ and Δ should take advantage of the task's structure. This is not only a matter of predictive quality. The predictor definition and SGD involve maximization problems, so the feature mapping and loss should be designed so that those computations can be carried out efficiently.

• Use a loss that expresses what matters for the task.
• Use a class-sensitive feature mapping that can achieve low approximation error.
• Keep the norm of the range of Ψ under control to help address overfitting.
• Ensure that the maximization problems required by prediction and SGD can be computed efficiently.
• Apply SGD only after the representation and loss have been defined.

Checkpoint Practice

• Describing ranking as four independent labels.

  A ranking output is an ordering in which position matters.

  Fix: Describe the output as a permutation of the original positions.

• Using SGD before defining the task representation.

  SGD learns the linear predictor only after Ψ and Δ have been specified.

  Fix: Define the class-sensitive feature mapping and task-specific loss first.

• Assuming a more expressive feature mapping is always better.

  The mapping should support low approximation error, but an excessively large range norm raises overfitting concerns.

  Fix: Balance task sensitivity with control of the range norm.

• Ignoring computational requirements.

  The predictor and SGD involve maximization problems that must be computed efficiently.

  Fix: Design Ψ and Δ to take advantage of the task's structure.