# Gradient Computation In Linear-Chain Conditional Random Fields Using The Entropy Message Passing Algorithm

Velimir M. Ili´ca,b,∗, Dejan I. Manˇcev b, Branimir T. Todorovi´c b, Miomir S. Stankovi´c c aMathematical Institute of the Serbian Academy of Sciences and Arts, Kneza Mihaila 36, 11000 Beograd, Serbia bUniversity of Niˇs, Faculty of Sciences and Mathematics, Viˇsegradska 33, 18000 Niˇs, Serbia cUniversity of Niˇs, Faculty of Occupational Safety, *Carnojevi´ca 10a, 18000 Niˇs, Serbia* ˇ

## Abstract

arXiv:1011.1478v2 [cs.AI] 30 May 2012 The paper proposes a numerically stable recursive algorithm for the exact computation of the linear-chain conditional random field gradient. It operates as a forward algorithm over the log-domain expectation semiring and has the purpose of enhancing memory efficiency when applied to long observation sequences. Unlike the traditional algorithm based on the forward-backward recursions, the memory complexity of our algorithm does not depend on the sequence length. The experiments on real data show that it can be useful for the problems which deal with long sequences.

Keywords: conditional random fields, expectation semiring, forward-backward algorithm, gradient computation, graphical models, message passing, sum-product algorithm 1. Introduction
[2], [3]. It makes use of dynamic programming, running with the asymptotical time complexity O(N
2T) and with the memory complexity O(NT), where T denotes the sequence length andN denotes the number of states classified. In spite of the time efficiency, it becomes spatially demanding when the sequence length is exceptionally large [14]. Furthermore, when it is used for the linear-chain gradient computation as in [12],
[17], [21], [23], [25] it requires the storage of all CRF transition matrices which increase the total memory complexity for O(N
2T).

The memory complexity can be reduced with modifications of the FB algorithm such as the checkpointing algorithm [11], [24] or with the re-computation of the transition matrices every time they are used (see section 3.3.). However, these techniques increase the computational complexity, while the memory complexity still depends on the sequence length. Another possibility is the use of forward-only algorithm [6], [20], [22], for which the matrices can be computed in runtime. This algorithm runs with constant memory complexity but it is computationally inefficient since it runs with the computational complexity O(N
4T).

In this paper we propose an algorithm for the exact computation of the linear-chain conditional random field gradient.

The algorithm is derived as a forward algorithm over the introduced log-domain expectation semiring, which means that its recursive equations can be obtained if real sums and products from an ordinary FB are replaced with products and sums from the log-expectation semiring. Accordingly, it can be seen as a numerically stable version of our previously developed Entropy Message Passing algorithm (EMP) [13], and it will also be called the EMP. Unlike the standard procedure, the EMP does not compute each marginal separately, but computes the gradient in a single forward pass by use of double recursion.

Preprint submitted to Elsevier September 3, 2018 Conditional random fields (CRFs) [17] are probabilistic discriminative classifiers which can be applied for labeling and segmenting sequential data. When compared with more traditional sequence labeling tools like hidden Markov models (HMMs), the CRFs offer the advantage by relaxing the strong independence assumptions required by HMMs. Additionally, CRFs avoid the label bias problem [17] exhibited by the maximum entropy Markov models and other conditional Markov models based on directed graphical models. However, these improvements are accompanied by a significant cost in time and space needed for the parameter estimation of CRF, especially for real-time problems like labeling very long sequences which appear in computer security [18], [28], bioinformatics [16], [19] and robot navigation systems [15].

The CRF parameter estimation is typically performed by some of the gradient methods, such as iterative scaling, conjugate gradient, or limited memory quasi-Newton methods [12],
[17], [21], [23], [25]. All these methods require the computation of the likelihood gradient, which becomes computationally demanding as the sequence length and the number of classes increase. The standard method for gradient computation [17] is based on the internal computation of CRF marginal probabilities by use of the forward-backward (FB) algorithm. The FB algorithm first appeared in two independent publications [4], [5], but it is better known from the subsequent papers 