On the inconsistency of separable losses for structured prediction (2023)

Abstract: In this paper, we prove that separable negative log-likelihood losses for structured prediction are not necessarily Bayes consistent, that is minimizing these losses may not result in a model that predicts the most probable structure in the data distribution for a given input. This fact opens the question of whether these losses are well-adapted for structured prediction and, if so, why.

## introduction modern natural language processing (nlp) heavily relies on machine learning (ml), where prediction models are learned by minimizing a loss function over the training data. as such, loss functions play a central role in the design of these systems and it is important to understand their statistical properties in order to guarantee that the corresponding training objectives are well defined. although this topic is well studied in the ml community @xcite @xcite @xcite @xcite @xcite @xcite , inter alia, there has been less focus on the structured prediction setting apart from a few recent works @xcite @xcite . in this paper, we emphasize the fact that, despite achievements in terms of accuracy, statistical behavior of loss functions used in practice for structured prediction in nlp are not always well understood. we illustrate this fact by proving that commonly used separable loss functions for named entity recognition (ner) and dependency parsing are not bayes consistent, meaning that training a model with these loss functions will not necessarily result in the prediction of the most the probable output for a given input in the data distribution. ## bayes consistency we denote inputs and outputs as @xmath0, respectively. we assume each @xmath1, i.e. @xmath2, 1} c , where c is problem dependent. for example, in the k multiclass classification case, we have @xmath3, where we use the shorthand [k] = {1, 2, ..., k}, and y is defined as the set of standard bases (one-hot vectors) of dimension k, meaning that |y | = k. more generally, the vector y is an indicator of "selected" parts in c and, in the structured prediction case, several parts can be jointly selected. note that it is usual to assume that the parts in c can depend on the input x. without loss of generality, we omit this detail as we will study loss functions in the pointwise setting. a scoring model @xmath4: @xmath5, e.g. the score of each class in a multiclass classification model. the actual prediction of the model is the output of maximum linear score: a loss function compares a vector of scores with an expected output. importantly, the 0-1 loss function is defined as follows: or, in other words, it is the probability of making an error when the classifier predicts the most probable class for each input. unfortunately, in practice it is not convenient to use the 0-1 loss ℓ as it is nonconvex and has null derivatives almost everywhere. instead, a surrogate ℓ can be used as a loss function: definition 1. a surrogate loss ℓ is said to be bayes consistent foot_0 if: note that this property can be checked independently for each input x (called pointwise bayes consistency) as we assume a rich enough class of functions f . in other words, we redefine the pointwise (optimal) surrogate risk as: for any x such that p(@xmath6, and similarly for the optimal bayes risk. the vector w should be interpreted as the model scores, i.e. @xmath7. ## negative log-likelihood loss the negative log-likelihood loss (nll), also known as the conditional random field loss @xcite , is defined as follows: in the following, we will refer to computing the log-sum-exp term of the nll loss as marginal inference due to its connection with marginal probabilities @xcite . theorem 1. under mild conditions on the data distribution, the surrogate loss ℓ (nll) is bayes consistent. proof. the optimal pointwise surrogate bayes risk is defined as: we substitute w(y) = ⟨w, y⟩ for all @xmath8: we denote w(y), ∀@xmath9, an optimal solution of the minimization. by first order optimality conditions, we have: to understand why equation 2 implies bayes consistency, note that: and the exponential function is strictly increasing. this means scores of outputs @xmath10, w⟩ are ordered in the same way as probabilities in the data distribution p(y|@xmath11. in other words, the most probable output in the data distribution will have the highest score with respect to w. the proof is a straightforward extension of the derivation for the multiclass classification case, see for example @xcite .2). interestingly, equation 2 also implies that the nll loss is strictly proper @xcite , i.e. the boltzmann distribution over structures in y parameterized by minimizer w is equal to the data distribution p(y|@xmath12. note that theorem 1 is not novel per se and a more in-depth study of nll losses for structured prediction can be found in @xcite . one limitation of the nll loss is that it is not (additively) separable 2 because of the log-sum-exp term. as such, this term is a bottleneck for parallel computation of the objective and doubly stochastic estimation of the training objective @xcite . a well-known solution is to rely on independent binary classification objectives, also known as onevs-all losses @xcite , section 6.1): in the case of multiclass classification problems, it can be shown that this objective is bayes consistent using similar arguments as in theorem 1. a different approach is the one-vs-each loss function that is also bayes consistent @xcite . unfortunately, these separable surrogates cannot be applied to structured prediction problems as the set y is often of exponential size with respect to the input length. although tractable algorithms for marginal inference exist for many cases, there are no known algorithms to compute the one-vseach or one-vs-all losses in an easily parallelizable fashion. as such, the nlp community often relies on token-separable losses, that is a nll objective that decomposes as a sum of independent losses, one per token in the input sentence. although these losses are easy to implement, we prove in the next sections that they are not bayes consistent for two common nlp problems. ## named-entity recognition problem definition. in this section, we focus on the flat ner problem using bio tags @xcite . without loss of generality, we assume there is a single mention label and that the input 2 a function f is additively separable if it can be written as @xmath13. we do not include parts corresponding to transitions (this is a unigram model), otherwise it would not be possible to derive a token-separable loss. inference algorithms. map and marginal inference can be realized using the viterbi and the forward-backward algorithms, respectively. although the time complexity of these algorithms is o(|l| 2 n) where l is the set of mention labels, they can be optimized to have a o(|l|n) time complexity as there is no transition score. the dynamic programming algorithm is nonetheless required in order to guarantee that condition (3) is satisfied. separable loss. as the dynamic programming algorithm is not parallelizable over input tokens, token-separable losses are often used in practice. 3 that is, the loss is reduced to a set of n multiclass classification losses: the optimal pointwise surrogate bayes risk for the separable loss is defined as: let w be an optimal solution. then, by first order optimality conditions: theorem 2. the token-separable loss for ner via bio tagging is not bayes consistent. proof. let @xmath14. then, by equation 3 we have w 1,@xmath15.65, w 1,@xmath16.35, w 2,@xmath17.4, w 2,@xmath18.3 and w 2,@xmath19.3. as such: log 0.65 + log 0.3 = ⟨ w, a⟩ < ⟨ w, b⟩ = log 0.65 + log 0.4, but @xmath20. therefore, the token-separable loss is not bayes consistent for ner, i.e. a scoring model minimizing the surrogate risk may not lead to predicting the most probable output in the data distribution. note that the inconsistency is not due to the fact that the parameterization of the model is "poor" (no transition scores). indeed, by equation 2, optimal scores w for the nll loss satisfy the following condition for all @xmath21: the following assignment for w satisfies this condition: w 1,@xmath22, w 1,@xmath23, w 2,@xmath24.2, w 2,@xmath25.3, and w 2,@xmath26.15. that is, minimizing the nll loss on this distribution results in a bayes consistent classifier, as expected. separable loss. the cubic-time complexity of mtt may be prohibitive in practice for training a model. moreover, the mtt relies on a computationally unstable matrix inversion and is arguably non-trivial to implement. hence, there has been interest in using simpler token-separable nll loss functions @xcite : this loss is a sum of multiclass classification nll losses, one per word in the sentence, and is therefore token-separable. as such, it can be efficiently parallelized on gpu and is trivial to implement in any ml framework. the optimal pointwise surrogate bayes risk for the token-separable loss is defined as: let w be an optimal solution. then, by first order optimality conditions: theorem 3. the loss ℓ (sep-dep) is not bayes consistent for distributions over dependency trees. proof. let @xmath27. then, by equation 4 we have: w 0,1 = log 0.7, w 0,2 = log 0.6, w 1,2 = log 0.4 and w 2,1 = log 0.3. as such: log 0.7 + log 0.4 = ⟨ w, a⟩ < ⟨ w, b⟩ = log 0.7 + log 0.6, but @xmath28. therefore, the token-separable loss is not bayes consistent, i.e. a scoring model minimizing the surrogate risk may not lead to predicting the most probable tree in the data distribution. note that using the (non-separable) nll loss will lead to a bayes consistent model on this distribution. indeed, by equation 2, optimal scores w satisfy the following condition for all @xmath29: exp⟨ w, y⟩ the following assignment for w satisfies this condition: w 0,1 = 0, w 0,2 = log 0.3, w 1,2 = log 0.4 and w 2,1 = 0. that is, minimizing the nll loss on this distribution results in a bayes consistent classifier, as expected. the single root constraint case is reported in appendix a. ## conclusion studying statistical properties of surrogate loss functions has not been a major interest in the nlp community, although there are exceptions @xcite . we proved that token-separable losses for ner and dependency parsing are not bayes consistent, which means that minimizing these losses will not necessarily lead to models that will predict the most probable output for a given input in the data distribution, even with infinite training data. in the dependency parsing case, @xcite experimentally observed that the structured nll loss leads to better results than the tokenseparable head selection loss. as such, our analysis provides a better theoretical understanding of these experiments. however, separable losses are widely used in state-of-the-art models, which suggests that future research should study why they work in practice. other types of separability have also been used for constituency parsing @xcite and semantic parsing @xcite , inter alia.