Automatic Assignment of Section Structure to Texts of Dutch Court Judgments

Context-Free Grammars (CFGs) are grammars where each rule is of the form

where $A$ is a single non-terminal symbol and $\alpha$ is any string of terminals and non-terminals, including the empty string $\epsilon$.

A Probabilistic Context-Free Grammar (PCFG) is then a Context-Free Grammar in which each rule has a probability assigned to it. A derivation of a sequence with a PCFG has a probability score attached to it, which is the product of the probabilities of all of the applied rules.

In our discussions, we assume probability scores to be real numbers between $0$ and $1$, with the common operations of multiplication and addition, but in implementation we use the Log semiring to avoid arithmetic underflow.

CFGs are said to be in Chomsky Normal Form (CNF) if all rules are of the following form:

Where $A$, $B$ and $C$ are non-terminal types, and $t$ is a terminal type. In the following, we use an extension of CNF with unary rules. In this extension, $t$ is either a terminal or non-terminal type.

A lot of work has been done in parsing (P)CFGs in applications of natural language processing and parsing programming languages. More recently, PCFGs have been used for other applications such as modeling RNA structures, as in Sakakibara et al. (1994, pp. 5112‑5120).

Listing 1 shows a simplified version of the grammar that we use to create the section hierarchy.

The Cocke–Younger–Kasami (CYK) algorithm is an algorithm for parsing Context-Free Grammars that was separately discovered by Kasami (1965), Younger (1967, pp. 189‑208) and Cocke (1969). The algorithm has time complexity of $\Theta (n^3\cdot \left | G \right |)$, where $n$ is the length of the input string and $\left | G \right |$ is the size of the grammar.

The standard version of the CYK algorithm is defined for ordinary context free grammars that are given in Chomsky normal form (CNF), but is easy to extend to include support for probabilistic and unary rules as well, as we do in this section. Note that any CFG may be transformed into an equivalent grammar in Chomsky normal form, and this also holds for probabilistic CFGs (Huang & Fu (1971, pp. 201‑224)). Also note that converting a grammar to CNF is not without cost: the increase in grammar size is $\mathrm O (\left | G \right |^2)$ for the best algorithm. The increase is linear if we use a variation of the CYK algorithm that works on grammars in binary normal form (2NF): see Lange and Leiß (2009, pp. 2008‑2010).

The CYK algorithm is a bottom-up parsing algorithm. The standard algorithm considers every substring from length $1$ to $n$, and keeps a list of all possible types for those substrings, along with their probabilities.

For substrings of length $1$ (individual words), we use the terminal rules in the grammar. For substrings of length $l>1$ (word sequences), we apply the production rules to every possible combination of two substrings of length $l-1$. This works, because CNF mandates that all production rules have 2 non-terminals. Every time we apply a rule, we multiply the probability attached to that rule and the probabilities of the constituent substrings.

In addition to binary production rules, we also allow unary rules in our grammar of the form $\text A \rightarrow \text B$, where $\text A$ and $\text B$ are both non-terminals. Extension of the algorithm is simple: after ordinary type assignment for substrings, we add those types to the list that result from applicable unary rules, if they produce a non-terminal that does not yet exist in the table with at least as much probability. We repeat until the cell does not change anymore.

A visual example of the result table can be found in Figure 10.

Evaluating performance on a parse tree is not as straightforward as it is for classification. Like in the previous chapter, we evaluate our grammar using an F-score, but notions of precision and recall are harder to define for constituency trees. To evaluate the parser, we use a metric known as PARSEVAL (due to Abney et al. (1991, pp. 306‑311)) with labeled precision and labeled recall as in Collins (1997, pp. 16‑23).

In this metric, precision and recall are defined as follows:

• Precision is the fraction of correct constituents out of the total number of constituents in the candidate parse
• Recall is the fraction of correct constituents out of the total number of constituents in the correct parse

Where 'correct constituent' means that each non-terminal node has the same label and the same yield, and yield is the ordered list of leaf nodes of a parse tree.

Over a set of 10 random documents, we report an average F₁-score of 0.92 and F₁-score of 0.93 (precision 0.93; recall 0.92).

Delving deeper into problematic parses, we see that there are a number of recurring types of errors that our parsing grammar makes. Firstly, it often occurs that subsections are not preceded by a full numbering. For example, consider a section numbering sequence such as the following:

1.
2.
3.1
3.2

Our grammar assumes that section 3.1 is a subsection of section 2, since section 2 is the first preceding supersection to 3.1. However, this not the desired result. The desired result would be to wrap the 3.X subsections in a section that represents section 3, even though there is no explicit numbering for section 3. This could be achieved with an extension to the section grammar.

Another issue is that the grammar has difficulty in deciding whether non-numbered sections should be subsections or not. Indeed, this can be difficult to determine based purely on typography.