PRILJ: an efficient two-step method based on embedding and clustering for the identification of regularities in legal case judgments

The retrieval of legal information from existing collections of legal documents can be supported by Information Retrieval (IR) techniques. Indeed, in the literature they have been already profitably used for different tasks. Existing approaches can mainly be categorized into methods that adopt manual knowledge engineering procedures (Brüninghaus and Ashley 2001; Silveira and Ribeiro-neto 2004) and methods that exploit NLP (Biagioli et al. 2005; Tomlinson et al. 2007). In general, NLP-based approaches applied to the legal sector are deemed to be superior, since they combine data-driven methods and embedding models when analyzing legal case judgments to directly identify legal concepts or different representations, such as tagged feature-value pairs or logical predicates (Maxwell and Schafer 2008; Zhong et al. 2020).

More recently, the big data paradigm, as well as the availability of big data analytics tools, is influencing legal authorities towards the publication of legal case documents through their online databases. On the other hand, researchers in the AI field are seizing this opportunity to enhance existing studies and contribute to the legal informatics field. For example, the work by Kumar et al. (2011); Trompper and Winkels (2016); Shulayeva et al. (2017); Mandal et al. (2017) prove the effort devoted to the development of complex intelligent solutions, to solve tasks such as legal document review, precedent analysis, or document similarity evaluation. Specifically, since various judgments lack semantic annotations, Trompper and Winkels (2016) proposed a method to assign a section hierarchy to Dutch legal case judgments: given a set of unstructured legal case judgments, the authors apply tokenization with linear-chain condition random fields (Sutton and McCallum 2012) to identify and label the roles of textual elements in a legal case judgment. Probabilistic context-free grammars are finally used to organize the text elements into a section hierarchy. Shulayeva et al. (2017) applied a machine learning method to automatically annotate sentences containing legal facts and principles in common law reports. The proposed approach relies on a feature selection step and on a Naïve Bayes multinomial classifier, to classify a given sentence as a principle, a fact or a neutral text. Although satisfactory results were achieved, experiments were limited to a corpus of only 50 reports.

Kumar et al. (2011) and Mandal et al. (2017) also contributed to the enhancement of the precedent analysis task. Both the proposed approaches were based on measuring the similarity among legal case judgments. In particular, Kumar et al. (2011) applied TF-IDF to represent documents, considering all the terms or only legal terms. Moreover, they also adopted the so-called bibliographic coupling similarity (that considers common out-citations), and co-citation similarity (that considers common in-citations). The authors reported that only the cosine similarity based on legal terms and the bibliographic coupling similarity provided accurate results when identifying similar legal case judgments, but generally observed a limited scalability of the proposed approach. On the other hand, Mandal et al. (2017) applied four different methodologies, namely, TF-IDF, Word2Vec, Doc2Vec, and Latent Dirichlet Allocation, to represent legal case judgments at different levels of granularity, such as summaries, paragraphs, sentences, or reasons for citation.

The adoption of embedding techniques to represent the textual content of legal documents has also been explored in LEGAL-BERT proposed by Chalkidis et al. (2020). LEGAL-BERT uses Bidirectional Encoder Representations from Transformers (BERT) (Devlin et al. 2019), to obtain contextual representations from legal documents. BERT uses a Transformer, an attention mechanism that learns contextual relations between words (or sub-words) in a text. Chalkidis et al. (2020) compared the performance of a general purpose pre-trained BERT model (Devlin et al. 2019), a fine-tuned BERT model with domain-specific corpora, and a BERT model totally learned from scratch from domain-specific corpora. The experiments performed by Chalkidis et al. (2020) confirmed that the fine-tuned version and the model trained from scratch from domain-specific documents show the best performance.

The same line of research has been explored in the Competition On Legal Information Extraction/Entailment (COLIEE), during which several tasks related to the legal domain have been solved with the support of embedding techniques. Among the approaches related to the present paper, it is worth mentioning BERT-PLI (Shao et al. 2020), that adopts BERT to capture the semantic relationships at the paragraph-level and then infers the relevance between two cases by aggregating paragraph-level interactions. Analogously to LEGAL-BERT, the BERT model in BERT-PLI is fine-tuned with a dataset related to the legal field.

It is noteworthy that, although the exploitation of embedding techniques has already been explored in the literature, to the best of the authors knowledge, the method proposed in this paper is innovative in the following aspects: i) it is the first method in the literature that exploits a two-step approach, based on clustering, to analyze textual content at document and paragraph levels in the legal domain; ii) it exploits an efficient Approximated Nearest Neighbor Search (ANNS) method to identify paragraph regularities; iii) it is much more robust to the presence of noise in the data, with respect to both baseline and state-of-the-art solutions, as we will show in our empirical evaluation (see Sect. 4.3).

Clustering generally refers to an unsupervised task consisting in grouping similar objects into clusters. More specifically, similar objects should fall into the same cluster, while dissimilar objects should fall into different clusters. Together with the design of advanced clustering algorithms (Berkhin 2002; Ester et al. 1996; Pio et al. 2012; Corizzo et al. 2019), the most critical research aspect of clustering is in the design of a proper representation of the objects/items at hand (Mikolov et al. 2013; Le and Mikolov 2014), as well as of similarity measures which allow the algorithms to understand how much two objects are similar/dissimilar.

Clustering techniques have also been adopted in the legal field. Despite the fact that legal documents are highly abstract, researchers managed to group similar legal documents on the basis of their topics, or on the basis of case citations and legal citations (Conrad et al. 2005; Lu et al. 2011; Raghav et al. 2015; Kachappilly and Wagh 2018).

Conrad et al. (2005) adopted a clustering tool (Zhao et al. 2005) to apply both hard and soft clustering on three large heterogeneous datasets to effectively generate a taxonomy while supporting legal firms in their knowledge management processes. Particularly promising results were achieved when adopting hierarchical clustering methods, where clusters are organized in a hierarchy, or overlapping clustering methods, where each document can possibly belong to multiple clusters.

Lu et al. (2011) reports a successful and scalable implementation of a soft clustering algorithm that is based on topic segmentation. Contrary to typical approaches based on lexical similarity, the authors exploit topics, document citations, and click-stream data from user behavior databases, to obtain a high-quality classification similar to that achieved by human legal experts.

Raghav et al. (2015) exploited citations and paragraph links to cluster legal case judgments from the Supreme Court of India, aiming to build efficient search engines. The authors used regular expressions to extract citations. Moreover, they define links between pairs of paragraphs belonging to different judgments showing a cosine similarity, computed on the basis of their TF-IDF representation, higher than a given threshold. A new clustering algorithm was also proposed, based on the Jaccard coefficient, and cluster prototypes were defined by selecting the legal case judgment exhibiting the highest similarity with the other legal case judgments within the cluster. Analogously, also Kachappilly and Wagh (2018) used case citations when clustering legal case judgments from the Indian Constitution. The proposed approach transforms the dataset into a binary matrix, indicating the presence or the absence of a citation of each case. Subsequently, the dataset is partitioned into groups through the classical k-means algorithm, using the Euclidean distance.

Although there are several works in the literature that considered the task of measuring the similarity among legal documents, and possibly identifying clusters thereof, the method proposed in this paper can be considered the first that simultaneously exploits advanced embedding techniques to capture the semantics and the context from the text. As mentioned in Sect. 1, these techniques are then used both in a two-step model to analyze the textual content at both document and paragraph level, and in an ANNS method to efficiently retrieve the most similar paragraphs with respect to a document at hand.

Word2Vec (Mikolov et al. 2013) is a word embedding method, namely a method to represent words as numerical feature vectors. Word2Vec learns a model to embed words by analyzing a collection of documents and by exploiting two different neural network architectures: Continuous-Bag-of-Words (CBOW) and Skip-gram (SG). Both architectures can capture rich syntactic and semantic relationships between words, but they are based on two different techniques: CBOW adopts a feed-forward neural network to predict a target (central) word from a given (surrounding) context, while SG aims to predict the surrounding words of a given target word. The first is generally faster to train and usually provides slightly better accuracy for frequent words, while the second is more accurate in the representation of rare words, at the price of a generally higher running time. However, previous experiments provided even discordant conclusions, depending on the specific datasets (Jin and Schuler 2015; Miñarro-Giménez et al. 2015).

In PRILJ, we adopt the variant based on CBOW, also because its learning process is conceptually closer to our final goal. In fact, a feed-forward neural network which can predict a target word from a given (surrounding) context well adapts to the task of identifying words and paragraphs to suggest while writing a document (according to the current context). This is not the case SG, where the task is rather different (predicting the context given a word).

Methodologically, given a sequence of words \(\langle w_{t-j},...,w_t,...,w_{t+j}\rangle\), representing the target word \(w_t\) and its context of size 2j, Word2Vec first maps each context word \(w_i\) to a one-hot vector representation \({\mathbf {w_i}}\) of size V, where V corresponds to the size of the vocabulary observed in the collection of documents. Each element of the vector corresponds to one word of the vocabulary and a generic word is then represented by a vector of 0s for all the vector values, except the value corresponding to the specific word, which is 1.

The neural network architecture aims to learn the optimal matrix \(S \in {\mathbb {R}}^{V\times E}\), where E is the desired size of the embedding space. The one-hot vectors of the context words are then multiplied by S. The obtained 2j vectors in the space \({\mathbb {R}}^E\) are averaged by the hidden layer to obtain the embedding of the target word \(w_t\). Formally, the hidden layer is computed as:The output layer, obtained by multiplying the embedding of the target word \(w_t\) by \(S^\top\), corresponds to the one-hot vector of \(w_t\) (see Fig. 4). This means that the neural network is learned so that it accurately reconstructs the one-hot vector of the target word \(w_t\), given the one-hot vectors of the context words.

Once the neural network has been trained using the training set, the obtained matrix S can be used to embed a given word into a numerical feature space of size E.

In our case, we learn a document embedding model from the training documents \(D_T\) (Algorithm 1, line 3), as well as k paragraph embedding models, one for each group of documents identified through k-means (Algorithm 1, line 12). An embedding model learned by Word2Vec can be queried for several purposes, but it natively provides an embedding for single words which represents the semantic of the word based on its context. In order to obtain an embedding for sequences of words (that may correspond to paragraphs or whole documents, in our case), different aggregation strategies can be adopted, including sum and mean, as suggested by Le and Mikolov (2014). In PRILJ, we obtain an embedding for the documents of the reference set (Algorithm 2, line 5) and for the target document (Algorithm 3, line 3), as well as for paragraphs of the reference set (Algorithm 2, line 9) and of the target document (Algorithm 3, line 8). For these purposes, we adopted the mean of the embeddings of the words.

Although Word2Vec can in principle be used to represent sequences of words, by adopting the mentioned aggregation strategies, it was not originally designed for this purpose. Consequently, Le and Mikolov (2014) proposed Doc2Vec, that is natively able to generate a vector representation of word sequences, where a sequence can be either a paragraph or a whole document.

Methodologically, Doc2Vec can exploit two different architectures, namely distributed memory (PV-DM) and distributed bag of words (PV-DBOW). Similar to CBOW, PV-DM aims to predict the word \(w_t\), given its context. However, the context is represented not only by the one-hot vector representations of its surrounding words, but also by a C-dimensional one-hot vector representation (\({\mathbf {seq}}\)) of the unique sequence ID (seq), where C is the total number of sequences. This vector encapsulates the topic shared by words in the same sequence. Conversely, PV-DBOW makes use of the SG architecture, where the one-hot vector representation of the unique ID associated with the sequence is fed to the input layer instead of the one-hot vector of \(w_t\).

For the same motivations for the adoption of CBOW in Word2Vec, in PRILJ, we adopt the PV-DM architecture in Doc2Vec, as shown in Fig. 5. The main differences with respect to the architecture shown in Fig. 4 are i) the presence of the C-dimensional one-hot vector (\({\mathbf {seq}}\)) in the input layer associated to the sequence ID (seq), and ii) the additional matrix \(D \in {\mathbb {R}}^{C \times E}\), which values are optimized together with those of the matrix S. Formally, in this case, the hidden layer is computed as:Analogously to the adoption of Word2Vec, we learn a document embedding model and k paragraph embedding models, and exploit them to embed documents and paragraphs, respectively. The main difference is that, in this case, we do not need any aggregation step to obtain the embedding of sequences of words from the embedding of single words.

In this subsection, we describe the strategy adopted in PRILJ to efficiently identify the top-n most similar paragraphs of the reference set, with respect to the paragraphs of the target document. A straightforward approach would consist in the computation of the pairwise cosine similarity between the vector representation of the paragraphs. However, such an approach would be computationally intensive. Namely, its time complexity would be \(O(n_r)\) for each paragraph of the target document, where \(n_r\) is the number of paragraphs of the reference set.

To deal with this computational issue, we propose an approach based on Annoy (Bernhardsson 2015), where the idea is to perform an approximated nearest neighbour search (ANNS). Methodologically, we perform two phases, i.e., index construction on the paragraphs of the reference set, and search, that occurs when we actually need to identify the top-n most similar paragraphs with respect to a paragraph of the target document. During the index construction, we build T binary trees. Each tree is built by partitioning the input set of vectors recursively, by randomly selecting two vectors and defining a hyperplane that is equidistant from them (see Fig. 6). It is noteworthy that even if based on random partitioning, vectors that are close to each other in the feature space are more likely to appear close to each other in the tree. It can be proved that this indexing step has a computational cost of \(O(T \times log_2(n_r)) = O(log_2(n_r))\).

During the search process, we traverse the binary trees by exploiting a priority queue. Specifically, each tree is recursively traversed, and the priority of each split node is defined according to the distance to the query vector (that is a paragraph of the target document, in our case). This process leads to the identification of T leaf nodes, where the query vector falls into. The distance between the query vector and the set of vectors falling into the identified leaves is finally exploited to return the top-n most similar paragraphs (Li et al. 2016). Computationally, also the search process takes \(O(T \times log_2(n_r)) = O(log_2(n_r))\).

Despite the fact that the results may not be identical to those of the exact search, previous experiments showed that its ability to face the curse of dimensionality leads to high-quality approximations, together with much higher efficiency.

In PRILJ, the index construction is performed once, on the set of all the paragraphs belonging to the reference set \(E_R\), while the search process is carried out for each paragraph of the target document (Algorithm 3, line 9).

In our experiments, we use a dataset made available by EUR-Lex¹ which, excluding empty documents, consists of 4,181 official public EU legal documents, having an average length of 2,739 words, related to both unconsolidated and finalized legal case judgments from 2008 to 2018. The total number of paragraphs in the dataset is 530,744, with an average of 22 words per paragraph. Each legal case judgment has a unique CELEX number which components are the EUR-Lex sector, the year, the document type and the document number. The CELEX number was used to fetch the legal case judgments. We extracted the textual content by ignoring HTML elements, while the \(<p>\) tag was used to identify the paragraphs. We applied the pre-processing steps mentioned in Sect. 3. We ignored words having a document frequency lower than 3, and we retained only paragraphs having at least 10 words.

Note that the considered dataset falls within the case-law sector and includes only legal case judgments by the Courts of Justice. Therefore, it does not include views delineated by the Advocate General and opinions on draft agreements given by the European Court.

All the experiments were performed in a 10-fold cross-validation (10-fold CV) setting, where 90% of the dataset is considered as training set and the remaining 10% of the dataset is considered as testing set, alternatively for 10 times. All the documents of the testing set were considered as target documents, while the reference set was built by constructing 20 replicas of each paragraph of the documents in the testing set, perturbed by introducing a controlled amount of noise. In particular, the noise was introduced by replacing a given percentage of words of each paragraph with random words selected from the Oxford dictionary². In our experiments, we considered different levels of noise, namely, 10%, 20%, 30%, 40%, 50%, and 60%, in order to evaluate the robustness of the proposed approach to different amounts of noise. We stress the importance of specifically evaluating this aspect, since noise (e.g., homonyms or misleading words) can be easily present in textual documents, and a robust approach should provide accurate results also when input documents are affected by potentially high amounts of noise.

In order to assess the specific contribution of the adopted embedding strategies, we compared the results obtained through Word2Vec and Doc2Vec with those achieved using a baseline strategy, i.e., the classical TF-IDF approach. In all the cases, we adopted a 50-dimensional feature vector. For TF-IDF, we selected the top-50 words showing the highest frequency across the set of legal case judgments.

We evaluated the performance of the two-step model implemented in PRILJ with different numbers of clusters, i.e., \(k \in \{\sqrt{|D_T |}/ 2,\sqrt{|D_T |},\sqrt{|D_T |} \cdot 2\}\). Note that \(k=\sqrt{|D_T |}\) is generally considered a default value for the number of clusters, when this has to be manually specified. In our analysis we also evaluate the sensitivity of PRILJ to the value of k.

We also performed an additional comparative analysis with state-of-the-art competitor systems. Specifically, we compared PRILJ with:Note that the above-mentioned competitors are able to represent paragraphs as feature vectors (i.e., they are embedding models), taking into account the semantics and the context of the textual content. Specifically, LEGAL-BERT-BASE, LEGAL-BERT-EURLEX and BERT-PLI represent paragraphs in a 768-dimensional feature space, while LEGAL-BERT-SMALL represents paragraphs in a 512-dimensional feature space. The embedding of each paragraph was computed as the mean of the embedding of its tokens.

Finally, we evaluated the effectiveness and the efficiency of the approach implemented in PRILJ for the identification of the top-n most similar paragraphs based on ANNS, with \(T = 100\) (number of trees). Specifically, we performed an additional comparative analysis against a non-approximated solution based on the cosine similarity, on a subset of 100 documents randomly selected from the dataset. This analysis was performed considering the best configuration in terms of the number of clusters k, and also focused on evaluating the advantages in terms of computational efficiency.

As evaluation measures, we collected precision@n, recall@n and f1-score@n, averaged over the paragraphs of target documents and over the 10 folds, with \(n \in \{5, 10,15,20,50,100\}\). Specifically, for each paragraph of a target document in the testing set, we considered as True Positives the number of correctly retrieved (perturbed) replicas from the reference set.

In summary, our experimental evaluation was performed along multiple dimensions of analysis, i.e., on the evaluation of: (i) the effect of different amounts of noise in the data, to evaluate the robustness of PRILJ to the presence of noise; (ii) the contribution of the embedding approaches implemented in PRILJ that also catch the semantics, with respect to the adoption of TF-IDF; (iii) the contribution provided by the two-step model with different numbers of clusters, with respect to the one-step model that does not exploit document clustering; (iv) the effect of the approximated nearest neighbor approach implemented in PRILJ, both in terms of effectiveness and in terms of efficiency.

In Tables 1, 2 and 3, we report the precision@n, the recall@n, and the f1-score@n results, respectively, measured with different embedding strategies and different levels of noise introduced in the dataset. The upper-left subtable shows the results obtained with the one-step model, while the other subtables show the results obtained by PRILJ with different numbers of clusters.

As expected, we can observe that in all the configurations the presence of noise negatively affects the results: the higher the amount of noise introduced, the lower the precision@n, the recall@n, and the f1-score@n. It is noteworthy that there is no difference in terms of conservativeness among all the considered approaches, namely, approaches obtaining a higher precision@n also obtain a higher recall@n and, accordingly, a higher f1-score@n. This interesting result allows us to outline clear conclusions (reported in the following of the section) about the most effective approaches (and their parameters) for the different phases implemented in PRILJ.

First, we can observe that, although the baseline based on TF-IDF obtained acceptable results, the adoption of the embedding methods implemented in PRILJ is significantly beneficial. Specifically, when adopting Doc2Vec, we observe an average improvement of \(17.68\%\) for the precision@n, \(17.71\%\) for the recall@n, and \(17.70\%\) for the f1-score@n. On the other hand, when adopting Word2Vec, we observe an average improvement of \(24.22\%\) for the precision@n, \(24.27\%\) for the recall@n, and \(24.29\%\) for the f1-score@n. This result confirms our initial intuition that catching the context and the semantics leads to significant improvements. Moreover, although Doc2Vec is natively able to work with word sequences, Word2Vec always obtains better results. This may be due to the fact that several paragraphs of different legal documents may share a similar topic, and the introduction of the unique sequence ID (seq) to associate the context with the document, as done by Doc2Vec, may generate overfitting.

From the results, it is possible to clearly identify the contribution of the two-step architecture we propose. Indeed, the results show that the proposed two-step model outperforms the one-step model, in all situations and for all the considered evaluation measures. We can also observe that the two-step model is much more robust to the presence of noise: although we can still observe a decrease of precision@n, recall@n, and f1-score@n when the noise amount increases, its impact is much less evident. In Fig. 7, we report a histogram that graphically shows the impact of the noise on the f1-score@20, with the two-step model (with different values of k) and with the one-step model. From the results, we can also observe that in general, the number of extracted clusters k seems to not significantly affect the results, even if the best results are observed with \(k = \sqrt{|D_T|} \cdot 2\). This means that the documents are distributed among several topics and that learning a different (more specialized) paragraph embedding model for each of them is helpful to retrieve significant paragraph regularities.

Focusing on the comparison with state-of-the-art systems, in Table 4 we report the f1-score@n results obtained by PRILJ (two-step model, \(k = \sqrt{|D_T|} \cdot 2\), Word2Vec) and by the considered competitor systems, with different levels of noise. From the results, we can easily observe that PRILJ always outperforms all the competitors, independently on the value of n of the f1-score@n measure, and independently on the amount of noise in the data. Moreover, as we can also observe in Fig. 8, the impact of noise is very evident on competitor systems. On the contrary, PRILJ appears very robust to the noise and, thus, adoptable in real contexts even when the amount of noise in the data is high. The significantly lower f1-score@n results achieved by the competitors, when documents are affected by high levels of noise, can be mainly due to the higher dimensionality of their embedding space (768 for LEGAL-BERT-BASE, LEGAL-BERT-EURLEX and BERT-PLI, 512 for LEGAL-BERT-SMALL), with respect to that adopted in PRILJ (50). Indeed, although BERT-based models exhibit very interesting results in several NLP tasks, including sentiment analysis, question answering, language inference, and named entity recognition (Devlin et al. 2019), their high-dimensional feature space makes them more susceptible to the curse of dimensionality on tasks based on the computation of distance/similarity, like in the task at hand. This result is coherent with what observed by Kumar et al. (2020), where the sensitivity of BERT-based models to the presence of noise has been investigated.

Finally, we specifically analyzed the performance of the ASSN approach implemented in PRILJ. We recall that we adopt an approximated approach for the identification of paragraph regularities to overcome computational bottlenecks. Since approximated approaches may usually lead to a loss in terms of accuracy, it is important to show that the high efficiency achieved by PRILJ does not come at the price of significantly worse results than those achievable through an exact search. As anticipated in Sect. 4.2, for this purpose, we performed a comparison with the exact computation of the top-n most similar paragraphs using the cosine similarity on a subset of 100 documents, with the PRILJ configuration that provided the best results (i.e., two-step model with \(k=\sqrt{|D_T |} \cdot 2\), see Tables 1, 2, 3). The f1-score results of this comparison are shown in Table 5, and graphically summarized in Fig. 9. The exact search based on cosine similarity leads to better results mainly when adopting TF-IDF with high levels of noise. On overall, the observed average improvement in terms of f1-score@n with respect to the adopted ANNS approach is \(0.6\%\), which can be considered negligible. On the other hand, the advantage in terms of efficiency is significant: the exact search required up to 1000x the time took by the ASSN implemented in PRILJ (see Table 6). This advantage is empirically evident even with the small subset of documents that we used, but the difference between their theoretical computational complexity (i.e., \(O(log_2(n_r))\) vs \(O(n_r)\), for each paragraph of the target document) provides a clear win to ANNS for large document collections. Indeed, while we were able to complete one run of the experiments on the full dataset on average in 1.5 hours, the adoption of the cosine similarity would have required some months on our server equipped with a 6-cores CPU@3.2 Ghz and 64GB of RAM.

The obtained results allow us to conclude that: i) PRILJ based on Word2Vec, the two-step model and \(k=\sqrt{|D_T |} \cdot 2\) provides the best overall results for the identification of paragraph regularities in legal case judgments; ii) the two-step model based on clustering implemented in PRILJ provides clear advantages, since it is able to properly model the different topics in the document collection and is very robust to the presence of noise; iii) the efficient ASSN strategy adopted by PRILJ provides results comparable to those achieved by an exact search, in a fraction of time. These conclusions make PRILJ a useful tool that can be adopted in real-world scenarios, for the accurate and efficient identification of paragraph regularities from large collections of legal case judgments, which can be profitably used in the redaction of similar legal documents.