Structured Logistic Loss and Partition Functions

From Structured Scores to Probabilities

A structured prediction model assigns a score to each possible output, such as a sequence, tree, or set of labels. A decoder can select the highest-scoring output, but scores by themselves are not probabilities: they need not be nonnegative or sum to one. Structured logistic loss gives the scores a probabilistic interpretation by exponentiating them and normalizing across the entire output space.

This normalization is global over valid structured outputs. The resulting denominator is called the partition function. It connects every candidate output to every other one: changing one score changes the normalized probabilities of the others as well.

Definition: Fix an input \(x\) and a finite, nonempty set of valid outputs \(\mathcal{Y}(x)\). Let \(S_\theta(x,y)\) be a real-valued score for output \(y\), depending on parameter \(\theta\). The partition function and globally normalized conditional probability are

Z_\theta(x)=\sum_{y'\in\mathcal{Y}(x)}\exp\{S_\theta(x,y')\}, \qquad p_\theta(y\mid x)=\frac{\exp\{S_\theta(x,y)\}}{Z_\theta(x)}.

For an observed output \(y\in\mathcal{Y}(x)\), the structured logistic loss is the negative conditional log-probability

\ell_\theta(x,y)=-\log p_\theta(y\mid x) =\log Z_\theta(x)-S_\theta(x,y).

Because the output set is finite and each score is real, \(Z_\theta(x)\) is finite and strictly positive. Thus the probabilities are well-defined, positive, and sum to one. In a linear-score model, the score takes the form \(S_\theta(x,y)=\theta^\mathsf{T}\phi(x,y)\), where \(\phi(x,y)\) is a feature vector. This parameterization makes both the gradient and the role of the partition function especially transparent.

Calculating the Normalization

Worked Example: Three Candidate Outputs

For a fixed input, suppose the valid outputs are \(a,b,c\), with scores \(0,\log 2,\log 3\), respectively. Calculate the partition function, the conditional probabilities, and the loss when the observed output is \(a\).

Exponentiating the scores gives weights \(1,2,3\). Therefore

Z= e^0+e^{\log 2}+e^{\log 3}=1+2+3=6.

Dividing each weight by six gives

p(a\mid x)=\frac{1}{6},\qquad p(b\mid x)=\frac{2}{6}=\frac{1}{3},\qquad p(c\mid x)=\frac{3}{6}=\frac{1}{2}.

These values sum to \(1\). For observed output \(a\), the loss is the negative logarithm of its probability:

\ell(x,a)=-\log(1/6)=\log 6.

The log partition function is \(\log 6\), and the observed score is zero, so the equivalent expression \(\log Z-S(x,a)\) also gives \(\log 6\).

The partition function is not an additional prediction. It is the quantity that converts a collection of unnormalized positive weights into a distribution. If the same constant \(c\) is added to every score for a fixed input, then every weight is multiplied by \(e^c\), and \(Z\) is multiplied by \(e^c\) as well. The conditional probabilities remain unchanged.

Gradients as Expected Features Minus Observed Features

Assume now that \(\theta\in\mathbb{R}^d\), that the feature vectors \(\phi(x,y)\in\mathbb{R}^d\) do not depend on \(\theta\), and that \(S_\theta(x,y)=\theta^\mathsf{T}\phi(x,y)\). For a fixed input and observed output, the gradient has a useful interpretation: it compares the model’s average feature vector to the feature vector of the observed output.

Theorem: For a finite output space and a linear score \(S_\theta(x,y)=\theta^\mathsf{T}\phi(x,y)\), the structured logistic loss is differentiable and

\nabla_\theta\ell_\theta(x,y) = \sum_{y'\in\mathcal{Y}(x)}p_\theta(y'\mid x)\phi(x,y') -\phi(x,y).

Its Hessian is

$$ \nabla_\theta^2\ell_\theta(x,y) = \operatorname{Cov}_{p_\theta(\cdot\mid x)}\!\bigl(\phi(x,Y)\bigr), $$ where \(Y\) has conditional distribution \(p_\theta(\cdot\mid x)\). In particular, the loss is convex in \(\theta\).

Proof. Write \(\phi_{y'}=\phi(x,y')\) for brevity. Since the sum defining \(Z_\theta(x)\) is finite, it can be differentiated term by term:

\nabla_\theta \log Z_\theta(x) = \frac{1}{Z_\theta(x)} \sum_{y'}e^{\theta^\mathsf{T}\phi_{y'}}\phi_{y'} = \sum_{y'}p_\theta(y'\mid x)\phi_{y'}.

The observed score has gradient \(\nabla_\theta(\theta^\mathsf{T}\phi(x,y))=\phi(x,y)\). Subtracting this gradient from the gradient of \(\log Z_\theta(x)\) proves the stated loss-gradient formula.

For the Hessian, let \(\bar{\phi}=\sum_{y'}p_\theta(y'\mid x)\phi_{y'}\). Differentiating a probability gives

\nabla_\theta p_\theta(y'\mid x) = p_\theta(y'\mid x)\bigl(\phi_{y'}-\bar{\phi}\bigr).

The observed feature vector is constant in \(\theta\), so differentiating the gradient leaves

\nabla_\theta^2\ell_\theta(x,y) = \sum_{y'}p_\theta(y'\mid x) (\phi_{y'}-\bar{\phi})(\phi_{y'}-\bar{\phi})^\mathsf{T}.

This is the covariance matrix of the feature vector under the model distribution. For any \(v\in\mathbb{R}^d\), its quadratic form is

v^\mathsf{T}\nabla_\theta^2\ell_\theta(x,y)v = \operatorname{Var}_{p_\theta(\cdot\mid x)} \bigl(v^\mathsf{T}\phi(x,Y)\bigr)\geq 0.

The Hessian is positive semidefinite, which proves convexity. \(\square\)

The gradient has a direct learning interpretation. If a feature appears more often under the model’s distribution than in the observed output, its expected value exceeds its observed value; gradient descent adjusts the parameter to reduce that discrepancy. The expectation is over complete outputs, not over independently normalized pieces unless the model’s structure justifies such a factorization.

Worked Example: A Two-Component Output with an Interaction

Let \(\mathcal{Y}=\{0,1\}^2\), write \(y=(y_1,y_2)\), and use the score

S_\theta(y)=\theta_1y_1+\theta_2y_2+\theta_{12}y_1y_2, \qquad (\theta_1,\theta_2,\theta_{12})=(\log 2,0,\log 3).

Calculate the distribution and loss for observed output \(y=(1,1)\), then calculate the gradient. The four outputs have scores and exponentiated weights as follows:

\begin{array}{c|c|c} y & S_\theta(y) & e^{S_\theta(y)}\\ (0,0)&0&1\\ (1,0)&\log 2&2\\ (0,1)&0&1\\ (1,1)&\log 2+\log 3=\log 6&6 \end{array}

Thus \(Z=1+2+1+6=10\). The probabilities in the same order are \(1/10,2/10,1/10,6/10\). The observed output has probability \(6/10=3/5\), so its loss is

\ell_\theta((1,1))=-\log(3/5)=\log(5/3).

The feature vector is \(\phi(y)=(y_1,y_2,y_1y_2)\). Under the model distribution, its three expected coordinates are

E_\theta[Y_1\mid x]=\frac{2+6}{10}=\frac{4}{5}, \qquad E_\theta[Y_2\mid x]=\frac{1+6}{10}=\frac{7}{10}, \qquad E_\theta[Y_1Y_2\mid x]=\frac{6}{10}=\frac{3}{5}.

The observed feature vector is \((1,1,1)\). Subtracting it from the expected vector gives

\nabla_\theta\ell_\theta((1,1)) = \left(\frac45-1,\frac7{10}-1,\frac35-1\right) = \left(-\frac15,-\frac3{10},-\frac25\right).

The interaction coordinate is included in the same calculation as the individual components. The globally normalized distribution accounts for the interaction through the score of \((1,1)\) and the shared denominator \(Z\).

A Scalar Gradient Calculation

Worked Example: Two Outputs and One Parameter

Suppose the output space is \(\{0,1\}\), with score \(S_\theta(y)=\theta y\), and set \(\theta=\log 3\). Find the probability of output \(1\), the loss and gradient when the observed output is \(0\), and verify the gradient from the loss formula.

The weights for outputs \(0\) and \(1\) are \(1\) and \(e^\theta=3\), so \(Z=4\) and \(p_\theta(1\mid x)=3/4\). When the observed output is \(0\),

\ell_\theta(x,0)=\log(1+e^\theta)-\theta\cdot 0=\log 4.

The feature is \(\phi(y)=y\). The expected feature is \(0(1/4)+1(3/4)=3/4\), while the observed feature is \(0\). Hence \(\nabla_\theta\ell_\theta(x,0)=3/4\). Direct differentiation agrees:

\frac{d}{d\theta}\log(1+e^\theta) = \frac{e^\theta}{1+e^\theta} = \frac34 \quad\text{at }\theta=\log 3.

The positive gradient means that a small gradient-descent step reduces \(\theta\), lowering the model’s probability for output \(1\) when the observed output is \(0\).

Why the Partition Function Matters

For a structured output space, the partition function sums over every valid candidate. It therefore determines both the probability assigned to the observed output and the model’s expected features in the gradient. If the set of outputs is large, computing \(Z_\theta(x)\) and those expectations can be computationally demanding; whether they can be computed efficiently depends on the structure of the scores and the output space.

A common mistake is to treat \(e^{S_\theta(x,y)}\) as the probability of \(y\). It is only an unnormalized weight: its value can exceed one, and the weights over outputs need not sum to one. The correction is to divide by the partition function. For example, the weights \(1,2,3\) in the first example are not probabilities; only \(1/6,2/6,3/6\) are.

A second useful check is invariance to a shared score offset. Replacing every score by \(S_\theta(x,y)+c\) multiplies the numerator and denominator of each conditional probability by \(e^c\), leaving the probability and loss unchanged. If a calculation changes the probabilities under such a common shift, the normalization has been applied incorrectly.

Key takeaway: Structured logistic loss is the negative log of a globally normalized conditional probability. Its gradient is the model’s expected feature vector minus the observed feature vector; for linear scores, its Hessian is a feature covariance matrix and is therefore positive semidefinite.

Check Your Understanding

Work through these questions using the definitions and calculations above.

Three outputs have scores \(\log 2,0,\log 5\). Find the partition function and the probability of the third output.
Why does adding the same constant to every output score leave the conditional probabilities unchanged?
For linear scores, state the gradient of the structured logistic loss and explain what each of its two terms represents.
In the two-component example, why does the interaction feature contribute to the expected feature vector?
What property of the Hessian establishes convexity in the linear-score parameter?