Automatic Assignment of Section Structure to Texts of Dutch Court Judgments

Directed Graphical Models (or Bayesian Networks) are statistical models that model some probability distribution over variables $v$ in a set $V$ which take values from a set $\mathcal{V}$. Loosely speaking, Directed Graphical Models can be represented as a directed graph $G$ where nodes represent the variables $v \in V$, and the edges represent dependencies. Directed graphical models factorize as follows:$p(V)=\prod _{v\in V}p(v|\pi(v))$Eq. 3.where $\pi(v)$ are the parents of node $v$ in graph $G$.

The class of Hidden Markov Models (HMMs) is one instance of directed models. HMMs have a linear sequences of observations $\mathbf x=\{x_t\}_{t=1}^T$ and a linear sequence of labels $\mathbf y=\{y_t\}_{t=1}^T$ (in HMM parlance, 'hidden states'), which are assignments of random vectors $X$ and $Y$ respectively, and $V = X\cup Y$. In HMMs, the observations $\mathbf x=\{x_t\}_{t=1}^T$ are assumed to be generated by the labels. One example of an application would be speech recognition, in which samples of the sound waves can be seen as observations and the actual phonemes as the labels.

To assure computational tractability, HMMs make use of the Markov assumption, which is that:

1. any label $y_t$ only depends on $y_{t-1}$, where the initial probability $p(y_{1})$ is given
2. any observation $x_t$ only depends on the label $y_t$; the observation $x_t$ is generated by label $y_t$.

A HMM then factorizes as follows:$p\left (\mathbf x,\mathbf y \right )= \prod _{t=1}^T p(x_t)p(y_t) = \prod _{t=1}^T p(x_t|y_t)p(y_t|y_{t-1})$Eq. 3.

If we return to the representation of HMMs in Figure 6, we see that the white nodes represent labels and the grey nodes represent the observations. Typically, observations are given and the labels need to be inferred. This is done from a given HMM by looping over all assignment vectors $\mathbf y\in Y$ and selecting $\mathbf y^*\in Y$ with the highest likelihood.

To find a model with plausible values of $p(x_t|y_t)$ and $p(y_t|y_{t-1})$, we typically perform a parameter estimation method such as the Baum-Welch algorithm on a set of pre-tagged observation-label sequences (Lucke (1996, pp. 2746‑2756)). This is called training the model.

The procedures for inference and parameter estimation for HMMs are very similar to those for LC-CRFs and are explain in more depth in the section on LC-CRFs.

Undirected Graphical Models are similar to directed graphical models, except we the underlying graph is an undirected graph. This means that Undirected Graphical Models factorize in a slightly different manner:$p( \mathbf x, \mathbf y)=\frac{1}{Z}\prod _A \Phi_A( \mathbf x_A,\mathbf y_A)$Eq. 3.where $Z=\sum _{\mathbf x, \mathbf y} ( \prod _A \Phi_A( \mathbf x_A,\mathbf y_A))$Eq. 3.

Intuitively, $p( \mathbf x, \mathbf y)$ describes the joint probability of observation and label vectors in terms of some set of functions $F = \{ \Phi_A\}$, collectively known as the factors. The normalization term $Z$ ensures that the probability function ranges between $0$ and $1$: it sums every possible value of the multiplied factors. In general, $\Phi_A \in F$ can be any function with parameters taken from the set of observation and label variables $A \subset V$ to a positive real number, i.e. $\Phi_A:A\rightarrow\ \mathbb{R}^+$, but we will use these factors simply to multiply feature values by some weight constant. Individually the functions $\Phi_A \in F$ are known as local functions or compatibility functions.

It is important to note that $F$ is specific to the modeling application. Our choice of factors is what distinguishes models from each other; they are the functions that determine the probability of a given input to have a certain output.

$Z$ is called the partition function, because it normalizes the function $p$ to ensure that $\sum_{\mathbf x,\mathbf y} p(\mathbf x,\mathbf y)$ sums to $1$. In general, computing $Z$ is intractable, because we need to sum over all possible assignments $\mathbf x$ of observation vectors and all possible assignments $\mathbf y$ of label vectors. However, efficient methods to estimate $Z$ exist.

The factorization of the function for $p(\mathbf x,\mathbf y)$ can be represented as a graph, called a factor graph, which is illustrated in Figure 7.

Factor graphs are bipartite graphs $G=(V,F,E)$ that link variable nodes $v_s\in V$ to function nodes $\Phi_A\in F$ through edge $e^{\Phi_A}_{v_s}$ iff $v_s\in \mathbf{arg} ( \Phi_A )$. The graph thus allows us to graphically represent how the variables interact with local functions to generate a probability distribution.

We define generative models as directed models in which all label variables $y \in Y$ are parents of the observation variables $x\in X$. This name is due to the labels "generating" the observations: the labels are the contingencies upon which the probability of the output depends.

When we describe the probability distribution $p( \mathbf y|\mathbf x)$, we speak of a discriminative model. Every generative model has a discriminative counterpart. In the words of Ng & Jordan (2002, pp. 841), we call these generative-discriminative pairs. Training a generative model to maximize $p(\mathbf y|\mathbf x)$ yields the same model as training its discriminative counterpart. Conversely, training a discriminative model to maximize the joint probability $p(\mathbf x,\mathbf y)$ (instead of $p(\mathbf y|\mathbf x)$) results in the same model as training the generative counterpart.

It turns out that when we model a conditional distribution, we have more parameter freedom for $p(\mathbf y)$, because we are not interested in parameter values for $p( \mathbf x)$. Modeling $p( \mathbf y|\mathbf x)$ unburdens us of having to model the potentially very complicated inter-dependencies of $p(\mathbf x)$. In classification tasks, this means that we are better able to use observations, and so discriminative models tend to outperform generative models in practice.

One generative-discriminative pair is formed by Hidden Markov Models (HMMs) and Linear-Chain CRFs, and the latter is introduced in the next section. For a thorough explanation of the principle of generative-discriminative pairs, see Ng & Jordan (2002, pp. 841).

On the surface, linear-chain CRFs (LC-CRFs) look much like Hidden Markov Models: LC-CRFs also model a sequence of observations along a sequence of labels. As explained earlier, the difference between HMMs and Linear-Chain CRFs is that instead of modeling the joint probability $p(\mathbf x,\mathbf y)$, we model the conditional probability $p(\mathbf y|\mathbf x)$.

This is a fundamental difference: we don't assume that the labels generate observations, but rather that the observations provide support for the probability of labels. This means that the elements of $x$ do not need to be conditionally independent, and so we can encode much richer observation patterns.

We define a linear-chain Conditional Random Field as follows:

Let

• $X, Y$ be random vectors taking values from $\mathcal{V}$, and $V = X\cup Y$
• $F=\{\Phi_1, \ldots\Phi_k\}$ be a set of local functions from variables (observation and labels) to the real numbers: $V \rightarrow\ \mathbb{R}^+$.

Each local function $\Phi_{k}(x_t,y_t,y_{t-1}) = \lambda_{k} f_{k}(x_t,y_{t},y_{t-1})$ where

• $x_t$ and $y_t$ be elements of $\mathbf x$ and $\mathbf y$ respectively, i.e., $x_t$ is the current observation and $y_t$ is the current label, and $y_{t-1}$ is the previous label, with some null value for $y_0$.
• $\mathcal F=\{f_k(y, y', x)\}$ be a set of feature functions that give a real-valued score given a current label, the previous label and the current observation. These functions are defined by the CRF designer.
• $\Lambda=\{\lambda_k\} \in \mathbb{R}^K$ be a vector of weight parameters that give a measure of how important a given feature function is. The values of these parameters are found by training the CRF.

For notational ease, we may shorten $\Phi_{k}(x_t,y_t,y_{t-1})$ as $\Phi_{k,t}$.

We then define the un-normalized CRF distribution as:$\hat{p}(\mathbf x, \mathbf y)=\prod_{t=1}^T\prod_{k=1}^K\Phi_k(x_t, y_t, y_{t-1})$Eq. 3.

Recall from our introduction on undirected graphical models that we need a normalizing constant to ensure that our probability distribution adds up to $1$. We are interested in representing $p(\mathbf y|\mathbf x)$, so we use a normalization function that assumes $\mathbf x$ is given and sums over every possible string of labels $\mathbf{y}$, i.e.:$Z(\mathbf x)=\sum_{\mathbf{y}}\hat{p}(\mathbf x, \mathbf y)$Eq. 3.and so$p(\mathbf y|\mathbf x)= \frac{1}{Z(\mathbf x)}\hat{p}(\mathbf x, \mathbf y) = \frac{1}{Z(\mathbf x)}\prod_{t=1}^T\prod_{k=1}^{K} \lambda_k f_k(x_t, y_t, y_{t-1})$Eq. 3.

When we recall that the product of exponents equals the logarithm of their sum, we can re-write $p(\mathbf y|\mathbf x)$ as

This is the canonical form of Conditional Random Fields.

McCallum & Sutton (2006, pp. 93‑128) show that a logistic regression model is a simple CRF, and also that rewriting the probability distribution $p(\mathbf x,\mathbf y)$ of an HMM yields a Conditional Random Field with a particular choice of feature functions.

As discussed in the previous section, we obtain parameters $\Lambda$ by training our CRF on a pre-labeled training set of pairs $\mathcal D=\{\mathbf{x}^{i},\mathbf{y}^{i}\}_{i=1}^N$ where each $i$ indexes an example instance: $\mathbf{x}^{i}=\{x^{i}_1, x^{i}_2, \cdots, x^{i}_T\}$ is a set of observation vectors, and $\mathbf{y}^{i}=\{y^{i}_1, y^{i}_2, \cdots, y^{i}_T\}$ is a set of labels for instance length $T$.

The training process will maximize some likelihood function $\ell(\Lambda)$. We are modeling a conditional distribution, so it makes sense to use the conditional log likelihood function:

Where $p$ is the CRF distribution as in Eq. 3.8:

Simplifying, we have:

Because it is generally intractable to find the exact parameters $\Lambda$ that maximize the log likelihood function $\ell$, we use a hill-climbing algorithm. The general idea of hill-climbing algorithms is to start out with some random assignment to the parameters $\Lambda$, and estimate the parameters that maximize $\ell$ by iteratively moving along the gradient toward the global maximum. We find the direction to move in by taking the derivative of $\ell$ with respect to $\Lambda$:

Where $\alpha$ is some learning rate between $0$ and $1$.

Thanks to the fact that the distribution $p(\mathbf{y}^{i}|\mathbf{x}^{i})$ is concave, the function $\ell(\Lambda)$ is also concave. This ensures that any local optimum will be a global optimum.

In our experiment, we use the Limited-memory Broyden–Fletcher–Goldfarb–Shannon algorithm (LM-BFGS), which approximates Newton's Method (see eg. Nocedal (1980, pp. 773‑782)). This algorithm is optimized for the memory-constrained conditions in real-world computers and also converges much faster than a naive implementation because it works on the second derivative of $\ell$.

The algorithmic complexity of the LM-BFGS algorithm is $O(TM^2NG)$, where $T$ is the length of the longest training instance, $M$ is the number of possible labels, $N$ in the number of training instances, and $G$ is the number of gradient computations. The number of gradient computations can be set to a fixed number, or is otherwise unknown. It is however guaranteed to converge within finite time, because of the concavity of $\ell$.

Given a trained CRF and an observation vector $\mathbf x$, we wish to compute the most likely label sequence $\mathbf y^*$, i.e. $\mathbf y^* = \text{argmax}_{\mathbf y}p(\mathbf y|\mathbf x)$. This label sequence is known as the Viterbi sequence. Thanks to the structure of linear-chain CRFs, we can efficiently compute the Viterbi sequence through a dynamic programming algorithm called the Viterbi algorithm, which is very similar to the forward-backward algorithm.

Substituting the canonical CRF representation of $p(\mathbf y|\mathbf x)$, we get:

We can leave out the normalization factor $\frac{1}{Z(\mathbf x)}$, because $\text{argmax}$ will be the same with or without:

Note that to find $\mathbf y^*$, we need to iterate over each possible assignment to the label vector $\mathbf y$, which would implicate that computed naively, we need an algorithm of $O(M^T)$, where $M$ is the number of possible labels, and $T$ is the length of the instance to label. Luckily, linear-chain CRFs fulfil the optimal substructure property which means that we can memoize optimal sub-results and avoid making the same calculation many times, making the algorithm an example of dynamic programming. We calculate the optimal path score $\delta_t(j)$ at time $t$ ending with $j$ recursively for $\Phi_t = \prod_{k=1}^{K} \Phi_{k,t}$:

where the base case

We store the results in a table. We find the optimal sequence $\mathbf y^*$ by maximizing $\delta_t(j)$ at the end of the sequence, $t = T$:

And then count back from $T-1$ to $1$:

This gives us the best label $y_t^*$ for each $t$, and so $\mathbf y^*$.

Using this trick, we reduce the computational complexity of finding the Viterbi path to $O(M^2 T)$.