Capturing Logical Structure of Visually Structured Documents with Multimodal Transition Parser

In this work, we propose to employ handcrafted features and a machine learning-based classifier as the transition parser. This strategy is more suited to our task than utilizing deep learning because (1) we can incorporate visual, textual and semantic cues, and (2) it only requires a small number of training data which is critical in the legal domain where most data is proprietary .

For each block, our parser extracts features from a context of four blocks and performs multi-class classification over the five transition labels. Since omitted changes targets of transition, we also omit omitted blocks in feature extraction. For $\mathit{trans}_{i}\neq\texttt{omitted}$, we extract features from $\left[b_{i-1},b_{i},b_{j},b_{j+1}\right]$ where $b_{j}$ is the first block after $b_{i}$ with $\mathit{trans}_{j}\neq\texttt{omitted}$. For $\mathit{trans}_{i}=\texttt{omitted}$, we extract features from $\left[b_{i-1},b_{i},b_{i+1},b_{i+2}\right]$. At test time, since we need to know the presence of omitted before feature extraction, we run a first pass of predictions to identify blocks with omitted, then use that information to dynamically extract features to identify other labels.

Our system can be customized to different types of documents by modifying the features. We have designed a feature set for each document type by visually inspecting the training dataset (Table 2). For Contract ^txt_en, we regarded space characters as horizontal spacing and blank lines as vertical spacing, which allowed us to define features that are analogous to those for PDFs.

While readers can reference our open-sourced code for the concrete implementation, we will discuss some of the features that have important implementation details. For a target block $b_{i}$:

Numbering transition (T1)

A categorical feature that itself is a heuristic transition parser. It identifies a numbering in each block and keeps a memory of the largest numberings by their types (i.e., its alphanumeric type and styling, such as IV. and (a)). It outputs (1) continuousif no numbering is found, (2) consecutiveif the numbering in $b_{i+1}$ is contiguous to the numbering in $b_{i}$, (3) upif not consecutive and there is a corresponding number in the memory, and (4) downif it is none of above and it is the first number in its numbering type . For example, B0 in Figure 1 is down as 1. is the first numbering type that it sees and “1” will be added to the memory. B1 and B2 are continuous as no numbering is found and B3 is consecutive as a number “2” is found in the same type as 1.. B4 is down as it contains a new numbering type.

Language model coherence (S1)

To determine if $b_{i}$ should be classified as omitted, it utilizes language model to classify whether it is more natural to have $b_{i}$ or $b_{i+1}$ after $b_{i-1}$. Specifically, we use GPT-2 Radford et al. (2019) to calculate language model loss $\ell(i,i-1)$ for $b_{i}$ given $b_{i-1}$ as a context (i.e., fed into the model but not used in the loss calculation). We then calculate $\ell(i,i-1)-\ell(i+1,i-1)$ as the feature. If it is more coherent to have $b_{i}$ after $b_{i-1}$, $\ell(i,i-1)$ will be smaller than $\ell(i+1,i-1)$ and the feature value will be negative. We also utilize $\ell(i+1,i)-\ell(i+1,i-1)$.

Similar text in similar position (V10)

Headers and footers tend to appear in similar positions across different pages with similar texts. For example, a contract may have the contract’s title on every pages at the same position. This feature is $1$ if there exists a block $b_{j}$ such that blocks’ overlapping area is larger than 50% of their bounding box (treating as if they are on the same page), and their edit distance is small⁷⁷7$d(b_{i},b_{j})/\max(len(b_{i}),len(b_{j}))<0.1$, where $d$ gives the Levenshtein distance and $len$ gives the length of text..

Line break before right margin (V4)

A Boolean feature that is $0$ if the block spans to the right margin and $1$ otherwise (i.e., breaks before the right margin). To distinguish the body and the margin of the document, we apply 1D clustering⁸⁸8We utilized a naïve 1D clustering, where it greedily adds elements from a sorted list to a cluster while the maximum difference of the elements is within a user-defined threshold. on the right positions of the blocks and extract the rightmost cluster with minimum members of six per page (to ignore headers/footers) as the right margin (Figure 3). This margin information is used in other features (V3, V6 and V7).

Larger line spacing (V8)

A Boolean feature that is $0$ if line spacing is normal and $1$ otherwise. To determine the normal line spacing, we apply 1D clustering on line spacings and pick a cluster with the largest number of members.

We also implement the pointer identification with handcrafted features and a machine learning-based classifier. Since a down transition creates a new level that a block can point back to, we extract all pairs of $\left[b_{j},b_{i}\right]$ ($b_{j}\in\mathcal{C}_{i}$) with $\mathit{trans}_{i}=\texttt{up}$, $\mathit{trans}_{j}=\texttt{down}$ and $j<i$. We then extract features from $\left[b_{j},b_{i}\right]$ and train a binary classifier to predict $p\left(\mathit{ptr}_{i}=b_{j}\middle|b_{j},b_{i}\right)$. In training, we use ground truth down labels to extract candidates $\mathcal{C}_{i}$. At test time, we aggregate $\mathcal{C}_{i}$ from predicted transition labels and predict the pointer by $\mathit{ptr}_{i}=\operatorname{argmax}_{b_{j}\in\mathcal{C}_{i}}p\left(\mathit{ptr}_{i}=b_{j}\middle|b_{j},b_{i}\right)$.

While our pointer points at a block with down ($b_{j}$), it is sometimes important to extract features from the first block in the paragraph that $b_{j}$ belongs to, which we will hereafter refer as $b_{head(j)}$. Using $b_{head(j)}$, we extract the following features from $\left[b_{j},b_{i}\right]$:

Consecutive numbering

Boolean features on whether a numbering in $b_{i}$ is contiguous to a numbering in $b_{j}$ and $b_{head(j)}$, respectively.

Indentation

Categorical features on whether indentation gets larger, smaller or stays the same from $b_{j}$ to $b_{i}$ and from $b_{head(j)}$ to $b_{i+1}$, respectively.

Left aligned

Binary features on whether $b_{j}$, $b_{i+1}$ and $b_{head(j)}$ are left aligned, respectively.

Transition counts

We count numbers of blocks $\{b_{k}\}_{j<k<i}$ with down and with up, respectively. We use these two numbers along with their difference as features. This is based on an intuition that a closer block with down tends to be more important.

Pointer features are also customizable, but we used the same features⁹⁹9More precisely, the pointer features are implemented slightly different for different document types, such as numbering being modified to Japanese for Contract ^pdf_ja, but they are intended to have similar functionalities. for all the document types.

While we call our system a “transition parser”, we do not employ a stack and instead employ the graph-based parser-like formulation for the pointer identification. We selected this strategy because of the recent success of graph-based parsers Dozat and Manning (2017); Zhang et al. (2019).

While we do report transition prediction accuracy, it is not a true task metric since it is rooted on our formulation of the task. Looking back at our initial motivation in Section 1, we introduce two sets of evaluation metrics.

The first set of metrics is rooted on IE perspective. For IE, it is important to identify ancestor-descendant and sibling relationships because it allows, for example, identifying a subject (in an ancestral block) and its objects (a decendant block and its siblings). Thus, we evaluate F1 scores for identifying pairs of blocks in (1) same paragraph, (2) sibling, and (3) ancestor-descendant relationships, respectively (Figure 5). Note that we do not include cousin blocks in the sibling relationship, because it is not clear whether cousin blocks have any meaningful information in the context of IE.

We use the second set of metrics to evaluate a system’s efficacy as a preprocessing tool for more general NLP pipelines. We evaluate paragraph boundary identification metrics since paragraph boundaries can be used to determine appropriate chunks of text to be fed into the NLP pipelines. We also report accuracy for removing debris with omitted.

We used five-folds cross validation for the evaluation.

We compared our system against the following baselines:

Numbering baseline

Hatsutori et al. (2017) This baseline detects numberings using a set of regular expressions and identifies dropping in hierarchy when the type of numberings has changed. Adopting Hatsutori et al. (2017) to our problem formulation, our implementation is the same as the feature “numbering transition (T1).”

Visual baseline

This baseline relies purely on visual cues; i.e., indentation and line spacing. For each pair of consecutive blocks, this baseline outputs (1) continuouswhen indentation does not change and line spacing is normal (as in feature V8), (2) consecutivewhen indentation does not change and line spacing is larger than normal, (3) downwhen indentation gets larger, and (4) upwhen indentation gets smaller . On up, it points back at the closest block with the same indentation.

PDFMiner

We use this popular open-source project to detect paragraph boundaries as in Bast and Korzen (2017). PDFMiner relies purely on geometric heuristics to detect paragraph breaks.

We used Random Forest Breiman (2001) as the transition and pointer classifiers, which is suited for categorical features that occupy the majority of our features. We did not tune hyperparameters of the Random Forest classifier and used default values of scikit-learn Pedregosa et al. (2011).

For language model coherence feature S1, we used GPT-2 medium¹⁰¹⁰10https://huggingface.co/gpt2 for English documents and japanese-gpt2-medium¹¹¹¹11https://huggingface.co/rinna/japanese-gpt2-medium) for Japanese documents.

Structure and preprocessing evaluations are shown on Table 3 and Table 4, respectively. Our system obtained micro-average structure prediction accuracy of 0.914 for Contract ^pdf_en, 0.908 for Law ^pdf_en, 0.828 for Contract ^txt_en and 0.940 for Contract ^pdf_ja, significantly outperforming the best baselines with 0.778, 0.827, 0.674 and 0.623, respectively. Our system performed the best with respect to F1 scores for all but one structure relationships.

The difference was even more significant for paragraph boundary detection. For Contract ^pdf_en, our system obtained a micro-average paragraph boundary detection F1 score of 0.953 that is significantly better than PDFMiner with an F1 score of 0.739. PDFMiner performed on par with our visual baseline and generally performed worse than our numbering baseline. This shows the importance of incorporating textual information to preprocess VSDs.

Micro-average transition label prediction accuracies were 0.951 (Contract ^pdf_en), 0.938 (Law ^pdf_en), 0.955 (Contract ^txt_en) and 0.923 (Contract ^pdf_ja).

We investigated the importance of each feature with greedy forward selection and greedy backward elimination of the features (Table 5). We can observe that our system makes a balanced use of the visual and textual cues. “Indentation (V1)”, “Larger line spacing (V8)” and “numbering hierarchy (T1)”, which partially represent the baselines, were ranked high in many cases. At the same time, other features such as “all capital (T10)” and “punctuated (T2)” were also contributing significantly to the accuracy, which made our system much superior to the baselines.

The feature importance revealed that the semantic cue (S1) was no more important than other cues. We suspect that the feature (which compares whether adjacent or non-adjacent block is more likely given a context) had fallen back to mere language model with the context being ignored in some cases, possibly due to GPT-2 not being fine-tuned on the legal domain.

We also conducted a qualitative error analysis. For Contract ^pdf_en, we found that our system was performing poorly on documents where they had bold or underlined section titles, followed by paragraphs without any indentation (predicted continuous instead of down). We believe incorporating typographic features would improve our system as implied by the success of the “all capital (T10)” feature.

For Contract ^txt_en, we found that blocks that are all capitals or are all underbars were misclassified as omitted. All capital words and underbars are frequently used to denote headers and footers, but they were used as section titles and input fields in these examples. Unlike for Contract ^pdf_en, we attribute this problem to lack of training data, as those should have been classified correctly with other features (such as T4 and T8) if the system had seen similar patterns in the training data.

Interestingly, we observed that the system tends to do better in documents that are hierarchically more complex. This may be because hierarchically complex documents tend to incorporate more cues to support humans comprehend the documents.