Finding Needles in Emb(a)dding Haystacks: Legal Document Retrieval via Bagging and SVR Ensembles Kevin Bönisch, Alexander Mehler Abstract We introduce a retrieval approach leveraging Support Vector Regression (SVR) ensembles, bootstrap aggregation (bagging), and embedding spaces on the German Dataset for Legal Information Retrieval (GerDaLIR). By conceptualizing the retrieval task in terms of multiple binary needle-in-a-haystack subtasks, we show improved recall over the baselines (0.849 > > 0.803 — 0.829) using our voting ensemble, suggesting promising initial results, without training or fine-tuning any deep learning models. Our approach holds potential for further enhancement, particularly through refining the encoding models and optimizing hyperparameters. [orcid=0009-0005-6962-2646, email=k.boenisch@outlook.com, url=https://www.texttechnologylab.org/team/kevin-boenisch/, ] *1 [orcid=0000-0003-2567-7539, email=mehler@em.uni-frankfurt.de, url=https://www.texttechnologylab.org/team/alexander-mehler/, ] keywords legal information retrieval ,support vector regression ,word embeddings ,bagging ensemble † † copyrightyear: 2024 † † copyright: Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). † † venue: LIRAI’24: 2nd Legal Information Retrieval meets Artificial Intelligence Workshop co-located with the 35th ACM Hypertext Conference, September 10, 2024, Poznan, Poland † † address: Text Technology Lab, Goethe University Frankfurt, Germany † † corresp: Corresponding author. 1 Introduction Information Retrieval (IR) fundamentally involves the process of identifying and extracting information units from an extensive collection, often in response to a specific query Salton and McGill 1983 . Legal Information Retrieval (LIR) represents the application of this concept within the legal domain, wherein the document collection consists of relevant judicial passages Sansone and Sperlí 2022 . Among these documents, some are particularly relevant to a given legal case (query), necessitating the task of identifying and retrieving these specific documents. Consequently, a variety of Natural Language Processing (NLP) methodologies, such as term frequency-inverse document frequency (TF-IDF) ( Salton 1989 ) (cf. Wehnert et al. 2021 for applying this in the legal domain) and BM25 ranking ( Manning et al. 2008 ) , are utilized to rank and compare collections of documents in order to retrieve the most pertinent ones. With the advent of the transformer architecture ( Vaswani et al. 2023 ) , language modeling has become a crucial component of LIR as well ( Nogueira and Cho 2020 ) . In this context, pre-trained bidirectional transformer models such as BERT ( Devlin et al. 2019 ) , RoBERTa ( Liu et al. 2019 ) and DeBERTa ( He et al. 2021 ) are especially valuable, as they contextually capture semantic features of potentially relevant documents through high-dimensional embedding vectors, making them distinguishable and comparable on a computational level. Through fine-tuning, these models can be further adapted to more domain-specific downstream tasks such as LIR, as exemplified by LEGAL-BERT ( Chalkidis et al. 2020 ) and DISC-LawLLM ( Yue et al. 2023 ) . Despite the significant potential these models offer for many NLP tasks ( Brown et al. 2020 ) , their lack of explainability remains a widespread criticism ( Luo and Specia 2024 ; Zhao et al. 2023 ) , which imparts them with a ”black box“ character that is critically scrutinized, particularly in the legal domain. In order to effectively train and apply these models, essential datasets tailored for (LIR) include those from the Legal Information Extraction and Entailment (COLIE) competition ( Rabelo et al. 2021 ) , SigmaLaw ( Sugathadasa et al. 2018 ) , FIRE 2017 IRLED ( Mandal et al. 2017 ) , and GerDaLIR ( Wrzalik and Krechel 2021 ) . To our knowledge, GerDaLIR stands as the sole German dataset for LIR, highlighting the predominance of English datasets and the absence of non-English retrieval models. To address this, we present results of our retrieval technique on the German GerDaLIR dataset, which surpass all baseline models. Our approach ensembles weak Support Vector Regressors (SVR) ( Hearst et al. 1998 ) , embeddings from a variety of pre-trained bidirectional transformers and employs Bagging ( Breiman 1996 ) techniques parallel to those used in Random Forests ( Breiman 2001 ) . In doing so, we frame the LIR problem akin to a needle-in-a-haystack task, as detailed in subsection 3.2 . Our results demonstrate an increase in recall ( 0.849 > 0.803 — 0.829) over the best baseline models, achieved without the need for fine-tuning any large deep learning models. Finally, we publish our soure code on GitHub 1 1 1 https://github.com/TheItCrOw/lirai24 . 2 Related Work For Information Retrieval (IR) in general, TF-IDF stands as one of the primary methodologies ( Salton and Buckley 1988 ; Beel et al. 2016 ) , owing to its simplicity and adaptability to various corpora and information sources. Consequently, within the aforementioned COLIEE competition, TF-IDF was widely used to directly retrieve or pre-process and pre-rank a given collection of documents ( Nguyen et al. 2020 ; Kim et al. 2023 ) . Following this, various BERT variants are employed for re-ranking ( Nogueira and Cho 2020 ) or downstream task fine-tuning ( Chalkidis et al. 2020 ) , often in combination with methodologies such as TF-IDF. Additionally, contextualized embeddings from bidirectional pre-trained transformers like BERT ( Kamalloo et al. 2023 ; Galke et al. 2017 ) are used for re-ranking or leveraging closeness metrics, such as cosine similarity, to fetch relevant documents. Finally, to enhance these models, feature engineering is applied to introduce potentially unique features, such as adding metadata to the documents, incorporating external data, or using model ensembles ( Wehnert et al. 2021 ) . In the following sections, we will outline in detail the relevant technologies used for our retrieval model. 2.1 Embeddings Transforming words and documents into a non-textual representation is a crucial task for nearly any NLP application. Among various methods, the vector space model introduced by Salton ( Salton et al. 1975 ; Salton 1989 ) is arguably the most relevant and influential approach for achieving this. As a result, much effort has been invested in projecting textual data into high-dimensional spaces to capture semantic and contextual features. This trend was exemplified in 2014 with Word2Vec ( Mikolov et al. 2013 ) and has since evolved with more recent models such as BERT and DeBERTa. These models generate high-dimensional embedding spaces for linguistic units, enabling spatial Euclidean measurements to capture semantic similarities and facilitate contextual retrieval or model training. 2.2 Supported Vector Machine Regression Support Vector Machines (SVM) are a popular machine learning tool for classification and regression (SVR), introduced by ( Vapnik 1995 ) in 1995. However, to our knowledge, they have not been widely used for LIR and IR in general. Akin to linear regression, Support Vector Machines (SVMs) aim to find the optimal hyperplane that effectively separates the two classes in the data. This hyperplane maximizes the margin, which is the distance between the hyperplane and the closest data points from each class, known as support vectors . SVR (Support Vector Regression) utilizes a similar concept where the margin is defined as an error tolerance of the model, known as the \epsilon -insensitive tube ( Vapnik 1995 ) . Given training data (\mathbf{x}_{i},y_{i}) for i=1,\ldots,n , SVR seeks to find a function f(\mathbf{x})=\mathbf{w}\cdot\mathbf{x}+b that approximates the true values y_{i} with minimal error, subject to the following constraints outlined in ( Vapnik 1995 , p. 153 onward) and ( Drucker et al. 1996 , p. 157) : y_{i}-(\mathbf{w}\cdot\mathbf{x}_{i}+b)\leq\epsilon+\xi_{i} (\mathbf{w}\cdot\mathbf{x}_{i}+b)-y_{i}\leq\epsilon+\xi_{i} where \xi_{i}\geq 0 are slack variables representing the deviation from the margin, and \epsilon controls the width of the tube. The objective is to minimize the following regularized error function: \frac{1}{2}\|\mathbf{w}\|^{2}+C\sum_{i=1}^{n}(\xi_{i}+\xi_{i}^{*}) subject to the constraints above, where C is a regularization parameter that balances the trade-off between the margin and the training error. The dual problem formulation involves computing Lagrange multipliers \alpha_{i},\alpha_{i}^{*} for each constraint, leading to the dual problem: \min_{\alpha,\alpha^{*}}\frac{1}{2}\sum_{i,j}(\alpha_{i}-\alpha_{i}^{*})(\alpha_{j}-\alpha_{j}^{*})\mathbf{x}_{i}\cdot\mathbf{x}_{j}+\epsilon\sum_{i}(\alpha_{i}+\alpha_{i}^{*})-\sum_{i}(y_{i}(\alpha_{i}-\alpha_{i}^{*})) with constraints \sum_{i}(\alpha_{i}-\alpha_{i}^{*})=0 and 0\leq\alpha_{i},\alpha_{i}^{*}\leq C for i=1,\ldots,n . The solution \mathbf{w} to the primal problem can be expressed in terms of the support vectors \mathbf{x}_{i} and their corresponding Lagrange multipliers \alpha_{i}-\alpha_{i}^{*} . In practice, SVR effectively handles nonlinear relationships through kernel functions, mapping the input space into a higher-dimensional feature space where a linear model is constructed. 2.3 Bagging Bootstrap Aggregating (Bagging), introduced by ( Breiman 1996 ) in 1996, is an ensemble learning technique designed to enhance model accuracy by combining multiple base learners which also provides the capability to partition the problem into smaller sub-problems. The key aspects of bagging involve: • Creating multiple subsets of the original dataset, thereby forming smaller sub-problems for base learners. • Training each base learner independently on these subsets. • Combining the predictions of the individual learners in the ensemble to make a final prediction. The strength of bagging lies in its ability to utilize an ensemble of smaller models ( Sharafati et al. 2021 ) , each trained on a subset of the dataset, particularly effective in scenarios with large feature sets and class imbalance. In such cases, overfitting can be a potential concern, and bagging can mitigate this risk effectively and hence improve generalization ( Qian et al. 2024 ) . 2.4 GerDaLIR GerDaLIR ( Wrzalik and Krechel 2021 ) is a G erman D ataset for L egal I nformation R etrieval based on the Open Legal Data platform. The dataset consists of 123,000 queries and 131,000 case documents, which are segmented into over 3 million passages. Each query is labeled with at least one document and hence multiple passages. The provided task is a precedent retrieval task based on case documents from the Open Legal Data 2 2 2 https://openlegaldata.io/ platform. The authors provide several baseline models for LIR, including TF-IDF, BM25, and deep learning approaches such as BERT re-ranking ( Nogueira and Cho 2020 ) . 3 Methodology In this section, we outline our approach to LIR on the GerDaLIR dataset, following the structure of a data science project report from start to finish, to demonstrate our findings and the chain of thought that led to our conclusions and final models. DistilRoBERTa RoBERTa_base RoBERTa_large DeBERTa_v3_large DistilBERT Longformer_base (a) Figure 1a: t-SNE plots of embedding spaces from different encoder models, generated for an exemplary sample of 10,000 collection passages. Each grey point represents a document passage in the collection. The red lines indicate the shortest distance from placed queries to their labelled relevant passages. Four queries were placed in each collection space, showing different distances to their relevant passages. While none of the relevant passages were the closest to their respective queries, it can be observed that in many cases the relevant passage is in close proximity. In particular, the longformer_base embedding space seems to capture the context best, as the entire collection forms a U-shaped cluster, and the distances from query to passage remain consistently the smallest, observable by the very short and barely visible red lines. deBERTa_base chunked Longformer_base chunked (b) Figure 1b: Exemplary t-SNE plots of the same document passages shown in Figure 1a, with the addition of chunking the passages into segments of similar lengths matching their overall average length, show that the average distance to the most relevant passage of each query is smaller compared to the spaces without chunking. 3.1 Explorative Data Analysis We begin by experimenting with various encoder transformer models. The intuition is to determine whether a given query is projected next to or at least very close to relevant documents in the collection embedding space, allowing for the possibility of retrieving documents based on their location in this space. Figure 1a displays excerpts of such a space as t-SNE ( Van der Maaten and Hinton 2008 ) plots. We tested a total of eight different models and placed exemplary query embeddings into the collection space to observe their relation to relevant passages. It can be seen that while none of the queries inserted into the collection space are positioned directly adjacent to their relevant document passages, the relevant passages are often in close proximity to the queries – this is consistent with the approach of Salton’s vector space model Salton 1989 . This is particularly evident when examining the longformer model ( Beltagy et al. 2020 ) , which appears to generate the most effective clustering for this task. The longformer was specifically trained to handle longer text sequences beyond lexical tokens or (short) sentences, which benefits the handling of queries and passages that typically range from two to six sentences in length. Another observation is that the embedding space is heavily influenced by the length of the passage or query. Texts of the same length, regardless of their semantic similarity, tended to be placed close together, while contextually more relevant texts were often placed further apart. We therefore chunked the passages into texts of equal length, which resulted in a better placement of relevant passages in relation to each other, as shown in Figure 1b. With regard to the LIR technique presented in this paper, we have not yet utilised this knowledge as our initial focus is on establishing a baseline. However, we intend to incorporate this approach in future iterations. Figure 1 : Modeling the flow of the needle-in-a-haystack training, we begin by partitioning the document space into several subsets (bagging), with each subset being assigned a separate SVR model for training. For each query in a subset, we identify the top k nearest passages through their vector spaces and concatenate their embeddings into a single feature embedding. Consequently, each query is associated with k-1 negative labels and one positive label. The SVR model is trained to find this single positive label within the haystack. This process is repeated for each subset and query. During prediction, each model in the group predicts a match for its respective subset. If only one model recognizes a positive match, the corresponding section is marked as relevant and output. 3.2 Finding the Needle in a Haystack Similar to other re-ranking techniques ( Nogueira and Cho 2020 ) , we use the embeddings generated by the longformer model, as it seemed to work best for our task, to formulate the LIR procedure as outlined in Figure 1 . 3 3 3 For the use of embedding methods in retrieval see also Karpukhin et al. 2020 . See Zhu et al. 2024 for a recent survey of embedding methods, especially with respect to large language models in IR. First, we generate an embedding for each passage, resulting in a 3.095.383\times 768 embedding matrix. This forms our collection embedding space. Next, we employ bagging and partition the embedding space into s subsets with some overlapping, where each subset is used to train its own SVR model, utilizing the Radial Basis Function (RBF) kernel. For this baseline, we partitioned it into 35 subsets with 60\% overlapping, resulting in a final model ensemble of 35 SVRs. For each query, we generate a 1\times 768 embedding and place it in the embedding space. Then, we collect the k nearest neighbors, which for this baseline is 50 . Our training assumes that the relevant passage to be retrieved is somewhere among these k passages. We then solve a binary regression training task for all of these k passages, each with k-1 negative labels and one positive label (the relevant passage among the k ). As features for the SVR model, we concatenate the query’s embedding vector with each passage, resulting in a k\times(2\times 768) feature matrix for the query. This process is repeated for each query in the subset and for each subset in the collection. This results in a \numprint{5034360}\times\numprint{1536} feature matrix for training. We then normalize the features with scikit ’s StandardScaler 4 4 4 See https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.StandardScaler.html ; this is just a z -score transformation. , before splitting it according to a 0.9/0.1 train-test split. The GerDaLIR dataset includes a separate test split on which our baseline is evaluated, allowing for a very large training split. For training, we utilize the RAPIDS cuML 5 5 5 https://github.com/rapidsai/cuml implementation of SVR to leverage the GPU resources, even for classical machine learning such as SVMs. Training was conducted on two NVIDIA Quadro RTX GPUs, each with 48GB of RAM. The entire process of calculating embeddings, performing bagging, creating the feature space, normalizing, and training took a total of two days, requiring 200GB of RAM swap. To enhance efficiency, we downscaled the precision of the matrices to 32-bit floats. 3.3 Results Method Mode MRR@10 nDCG@20 Recall@100 Recall@1000 TF-IDF P 0.333 0.375 0.651 0.768 D 0.336 0.386 0.701 0.809 BM25 (k1=1.20, b=0.75) P 0.365 0.409 0.693 0.800 D 0.386 0.434 0.734 0.827 BM25 tuned (k1=0.51, b=0.72) P 0.372 0.417 0.703 0.803 BM25 tuned (k1=0.90, b=0.98) D 0.391 0.439 0.737 0.829 WCS - GloVe P 0.242 0.278 0.539 0.695 D 0.134 0.166 0.420 0.625 WCS - fastText P 0.257 0.295 0.582 0.726 D 0.153 0.188 0.468 0.668 Neural Re-ranking - BERT P 0.416 0.465 0.745 0.789 Neural Re-ranking - ELECTRA P 0.436 0.481 0.743 0.789 Method Mode Recall SVR Ensemble P 0.849 Table 1 : The baseline measures of the GerDaLIR dataset are compared to our preliminary LIR technique. In this context, Mode P and D refer to passage-wise and document-wise retrieval, respectively. Metrics such as MRR and nDCG have not yet been evaluated on our ensemble. The original authors utilized Recall@100 and Recall@1000 for re-ranking, a restriction that we do not impose. The results indicate that our preliminary ensemble surpasses all baseline measures. Figure 2 : Model Accuracy Metric Value Test set accuracy 0.9966 Precision 0.9987 Recall 0.8527 F1-score 0.9199 Figure 3 : Classification Report Class Precision Recall F1-score Support 0 1.00 1.00 1.00 491915 1 1.00 0.85 0.92 11521 Accuracy 1.00 (503436 samples) Macro avg 1.00 0.93 0.96 503436 Weighted avg 1.00 1.00 1.00 503436 Table 1 presents the results of the GerDaLIR dataset baselines alongside our ensemble. In addition to recall metrics, further details of our training results are outlined in Figure 3 and 3 . The seemingly perfect scores for class 0 are a result of the nature of the needle-in-a-haystack task and should not be misinterpreted as indicating perfect model accuracy. Given that we sample, on average, k-1 negative labels for each positive label, the precision and recall for this highly imbalanced class are distorted. Therefore, it is necessary to focus primarily on the results for class 1 , where it is evident that even with a relatively small k of just 50 , our ensemble consistently identifies relevant passages with high recall, precision, accuracy, and F1 score. From this point of view, we now outline our decision to select the SVR of all ML models as our ensemble models: • The ever-present danger with high-dimensional data is overfitting ( Tsuda and Imaizumi 2023 ) . This risk is exacerbated by the fact that for each query we sample, on average, k-1 negative samples with only one positive sample. One way to mitigate such overfitting is to utilize L1 or L2 regularization ( Ng 2004 ) , which SVR implements by default. • The SVR approach involves mapping data into a higher-dimensional space than the original data set, in order to achieve better separability. From the beginning, we found that concatenating embedding vectors as features is favorable, making SVR a very suitable model for our purposes. • Because of kernel functions such as RBF, SVRs are able to capture nonlinear relationships ( Ghosh et al. 2019 ) . This capability is crucial for the needle-in-a-haystack task at hand, as a linear function would not be sufficient to separate the two classes. But this is also a reason why overfitting is made easier. A variety of nonlinear functions should therefore be experimented with here. • The RAPIDS implementation gave us access to traditional stochastic machine learning models that run on GPUs, which greatly accelerated the training process. Given the large feature space, this step was critical. Finally, as previously mentioned, SVRs are significantly more interpretable than deep learning models, providing greater transparency. 4 Conclusion and Future Work We showcased a novel approach for LIR, combining several machine learning methods such as SVR, bagging, and embedding spaces. While these initial results are promising, we need to work on the following areas: 1. As demonstrated by our exploratory data analysis in subsection 3.1 , the embedding spaces heavily depend on the length of the texts. If we were to further partition the passages and queries into texts of equal length, the overall ensemble and retrieval process could benefit from it. Further investigation into this approach is necessary. Additionally, our approach is based on the observation that relevant passages are generally proximate to the queries within the embedding space. Nevertheless, as illustrated in Figure 1a, there are instances where outlier passages are positioned far from their corresponding queries, making it exceedingly difficult for our ensemble model to identify them. This is one of the key constraints that we need to address, particularly through the investigation of the impact of increasing the value of k . 2. Due to time and hardware constraints, we had to opt for a relatively small k=50 for first level retrieval. Increasing the radius of the initial retrieval layer, within which the models search for relevant information, could significantly enhance recall. 3. The initial idea was to utilize multiple embedding spaces generated by various encoder models and concatenate them, thereby further increasing the feature space by higher dimensions. This approach has proven effective in several high-profile NLP competitions 6 6 6 https://www.kaggle.com/competitions/feedback-prize-english-language-learning/discussion/369457 . For these preliminary results, we opted for a single embedding model, but we aim to expand this approach. Finally, we recognize the need for more German-based models and approaches, particularly within the field of law. The encoding models currently employed primarily process English text and rarely specialize in legal domains. While fine-tuned versions like LEGAL-BERT exist, they predominantly cater to non-German texts. The development of a German pre-trained encoder model, akin to LEGAL-BERT, could help bridge this gap and presents a promising avenue for future research. Our present approach combines SVMs with transformer-based embedding models to develop an appropriate feature space for the classification task at hand. The very simple method evolves as a process in which better and better embedding models can improve the second main part of our method, just as more efficient classification methods can improve the classical ML part that makes up the first main part of our approach. The obvious question as to why we do not rely directly on fine-tuning a pretrained embedding model lies in the transparency that the SVM-based approach offers us as a classification tool. This transparency is necessary because we divide the original document space into overlapping subspaces that compete, so to speak, for the processing of a query by the classifiers assigned to them. Thus, we divide the overall task into a series of subtasks, each of which can be transparently processed by classifiers, where the partitioning of the overall document space can reflect the specific topological conditions of the underlying embedding space, providing additional transparency. However, by using more and more information about the topology of the document space, the classifiers can adapt more and more efficiently to its structure, eventually becoming less and less complex (below the level of RBFs used so far). In this way, we envision an approach that takes advantage of both the ongoing process of inventing ever more expressive embedding spaces and models for topology preserving segmentation of such spaces as a prerequisite for training ever more efficient classifiers. This may eventually contribute to a kind of information retrieval that combines transparency with expressiveness in terms of numerical representation of documents – very much in the spirit of Salton’s classical vector space model.