Constrained conditional models

Overview

Some outputs are structures made of parts that depend on each other, such as an expression tree built from numbers in a text. Training one model for the whole structure needs jointly annotated data, which is expensive. Constrained conditional models (CCMs) take a different route: several simple components are learned independently, and the structure is chosen at inference time by combining their scores while respecting constraints on the output. The paper under this page uses the "L+I" scheme of CCMs, which learns independent local components and combines them at inference 1608.01413 §2. The authors cite the general CCM framework to Chang et al. (2012); no card exists for that paper, so this page draws only on the 1608.01413 card.

The invariant the variants share is that the final output must satisfy the constraints, and that the local scores are summed over the parts of that output. The paper's objective is a weighted sum of relevance scores for unused quantities and pairwise scores for used quantities, maximised over the expressions that pass the constraints 1608.01413 §4.1 eq. 3.

Variants

Independent local classifiers with a beam search (1608.01413)

Two classifiers are trained separately on gold annotations: a binary SVM that scores whether each quantity is needed, and a multiclass SVM that scores the operation at the lowest common ancestor of each quantity pair 1608.01413 §4.3 1608.01413 §4.4. Inference is a bottom-up beam search with beam size k = 200 that keeps the top candidates at each step and returns the best tree passing the constraints [arxiv:1608.01413 §4.1]. Card: Solving General Arithmetic Word Problems.

The paper's constraints are a positive answer and, for "how many" questions, an integral answer 1608.01413 §4.1. The paper reports accuracy for each constraint on its own and for both together, on three datasets:

These are the authors' numbers, on their own dataset versions [arxiv:1608.01413 §5.1]. The table shows that the effect of a constraint depends on the dataset.

When to use which

The only variant in the wiki so far is the one above, so the choice here is about whether the CCM pattern fits your problem. The constraints that the paper actually used are the ones you can check directly on a candidate output. Use this pattern when:

Do not expect the pattern to remove the need for good features. The paper's error analysis attributes most errors to the quantity-schema extraction step, which feeds the classifiers 1608.01413 §5.5.

Implementation sketch

Language-agnostic pseudocode of the common core. The paper's variant uses SVMs and an expression tree; the other parts are generic.

# Train each local component on its own gold labels  [arxiv:1608.01413 §4]
relevance_model = train_binary(quantities, gold_relevance)
pair_model = train_multiclass(quantity_pairs, gold_lca_label)

# At inference, score every part of a candidate structure  [arxiv:1608.01413 §4.1]
def score(candidate):
    # Sum local scores over the parts of the candidate  [eq. 3]
    return (w_rel * sum(relevance_model.score(q) for q in unused(candidate))
            + sum(pair_model.score(p) for p in pairs(candidate)))

# Hard constraints, checked on the candidate  [arxiv:1608.01413 §4.1]
def feasible(candidate):
    # Positive answer
    if candidate.value < 0:
        return False
    # Integral answer, only when the question asks "how many"
    if is_how_many(question) and not is_integer(candidate.value):
        return False
    return True

# Beam search over partial structures, keeping the top k  [arxiv:1608.01413 §4.1]
beam = [empty_structure()]
while not all(s.is_complete() for s in beam):
    expanded = [t for s in beam for t in s.extensions()]
    beam = top_k(expanded, k=200, key=score)

# Return the best feasible structure; if none is feasible, the paper
# falls back to the top of the beam  [arxiv:1608.01413 §4.1]
feasible_ones = [s for s in beam if feasible(s)]
best = max(feasible_ones, key=score) if feasible_ones else beam[0]

Where variants differ: the scoring of partial structures inside the beam is not stated in the paper, so the top_k key above is a choice you must make 1608.01413 §4.1.

Contradictions

None known across the cards: only one card currently cites this concept. Within the single paper, the constraints do not help on every dataset: on AI2 the no-constraint baseline (77.7) is above the full system (72.0), while on IL and Commoncore the full system is the best result tab. 6. The authors report the AI2 gain for the positive constraint alone (78.0) as the best AI2 number, not the full system 1608.01413 §5.4.

Papers

• Solving General Arithmetic Word Problems: applies the L+I scheme with a relevance classifier, a pairwise operation classifier and a constrained beam search to multi-step arithmetic word problems.