go to DevelopmentPage

Structure Prediction Framework

This page describes the framework for structure prediction used in treeler. The framework is based on linear prediction methods, ported to the case where the output domain is structured.

The core algorithms in treeler are generic with respect to the structures they predict. This section describes generic algorithms for structure prediction and their interfaces to abstract objects.

  • X is the class of generic input structures. x in X is an input instance.
  • Y is the class of generic output structures. An example is a pair (x,y) of input/output structures. We denote as Y(x) the structures y in Y that are valid assignments for x in X.
  • A model associates X with Y. It defines scores of pairs (x,y) and provides methods to map x to y.

Factorized Mappings

We assume a that scores of (x,y) pairs factorize into abstract parts of the paired structure. This factorization will allow efficient mappings.

Let x be a pattern, we assume a function R(x) that enumerates the set of parts that can be assigned to x. We also assume a scoring component, that given a pattern and a set of parts, computes a score for each part.

  • R is space of parts, we use r in R
  • Abusing notation, we also use R as the factorization:
    • R(x,y) enumerates the parts of a pair (x,y)
    • R(x) enumerates the parts that x can take, R(x) = union { y in Y(x) } R(x,y)
  • score(x,r) is a score of x and part r. Then score(x,y) = sum {r in R(x,y)} score(x,r)
    • Linear Scoring. Features phi(x,r), and parameters W in the same dimensionality. score(x,r) = <w, phi(x,y)>
  • Inference methods. Compute mappings between X and Y.
    • Argmax, k-best, marginals. Via semirings (max, sum, marg). Operators. Hypergraphs. Derivations
  • Learning methods. Given a training collection of (x,y) pairs, learn a scoring function.

Abstract Algorithms


  • Defines R
  • Requires X, Y
  • Implements
    • R(x,y), enumeration of parts
    • R(x), enumeration of parts
    • map<T>(r,T), a mapping from part r to a T object
  • Types
    • Dense, requires index
    • Sparse, requires hash


  • Types
    • Lazy


  • Defines S
  • Requires X, Y, R
  • Implements
    • score(x,r)
    • score(x,y) = sum { r in G(x,y) } score(x,r)

=== Linear Scoring ====

  • Linear Prediction Scoring: a specific type of scoring will compute scores using S(x,r) = <w, phi(x,r)>, where phi(x,r) is a feature vector and w is a parameter vector of the same dimensionality


  • Parser, given x and a scoring S, computes best y, k-best ys, or marginals on factors


  • Learning algorithms, given a training algorithm and a feature definition, obtain a w to compute part scores