# Diversify and Conquer: Bandits and Diversity for an Enhanced E-commerce
Homepage Experience

Sangeet Jaiswal  Myntra Designs Pvt LtdBangaloreIndia
<EMAIL_ADDRESS>,  Korah T Malayil  Myntra Designs Pvt
LtdBangaloreIndia<EMAIL_ADDRESS>,  Saif Jawaid  Myntra Designs Pvt
LtdBangaloreIndia<EMAIL_ADDRESS>and  Sreekanth Vempati  Myntra
Designs Pvt LtdBangaloreIndia<EMAIL_ADDRESS>
(2023)

###### Abstract.

In the realm of e-commerce, popular platforms utilize widgets to recommend
advertisements and products to their users. However, the prevalence of mobile
device usage on these platforms introduces a unique challenge due to the
limited screen real estate available. Consequently, the positioning of
relevant widgets becomes pivotal in capturing and maintaining customer
engagement. Given the restricted screen size of mobile devices, widgets placed
at the top of the interface are more prominently displayed and thus attract
greater user attention. Conversely, widgets positioned further down the page
require users to scroll, resulting in reduced visibility and subsequent lower
impression rates. Therefore it becomes imperative to place relevant widgets on
top. However, selecting relevant widgets to display is a challenging task as
the widgets can be heterogeneous, widgets can be introduced or removed at any
given time from the platform. In this work, we model the vertical widget
reordering as a contextual multi-arm bandit problem with delayed batch
feedback. The objective is to rank the vertical widgets in a personalized
manner. We present a two-stage ranking framework that combines contextual
bandits with a diversity layer to improve the overall ranking. We demonstrate
its effectiveness through offline and online A/B results, conducted on
proprietary data from Myntra, a major fashion e-commerce platform in India.

Recommender Systems, Widget Ranking, Contextual Bandits, Content Divesity

††copyright: acmcopyright††journalyear: 2023††doi:
XXXXXXX.XXXXXXX††conference: 17th ACM Conference on Recommender Systems,
Singapore; 18th-22nd September 2023; Singapore††ccs: Information systems
Recommender systems††ccs: Computing methodologies Online learning
settings††ccs: Computing methodologies Reinforcement learning††ccs:
Information systems Computational advertising

##  1\. INTRODUCTION

In the world of e-commerce, the website or app real estate holds significant
value and serves as a key catalyst in shaping user experience, engagement, and
conversion rates. Most of the homepages have distinct sections, comprising
various widgets that feature diverse content such as product recommendations,
monetization products and ads, promotions, and sale details. As the number of
widgets increases, the demand for a systematic and relevant display order
becomes more pronounced. Our data reveals that, on average, users scroll down
the homepage up to three times and click on widgets within the first two
scrolls.

Addressing this challenge posed a few hurdles in our context, Widgets are
owned by different teams, and slotting them properly requires domain knowledge
and validation through A/B tests, which is time-consuming and also not
feasible sometimes. The notion of a widget ID is not tangible since the same
widget can be represented with different widget IDs in different layouts.
Widgets are also heterogeneous in nature, for example, they can be banners,
awareness campaigns, product carousels, engagements (videos), order tracking
cards, etc. The contents of these widgets are powered by different
recommendation models and are personalized to the user. Hence the
representation of these widgets needs to be learned without taking the content
into consideration. Specifically, the particular brands or products within
these widgets are not available as signals to the ranker due to system
constraints.

For this reason, we have engineered new features such as Core theme, Widget
intent, etc. to identify what type of content is being showcased through the
widgets. These have been instrumented as mandatory fields to be filled by
business teams while creating/deploying new widgets and layouts. Existing
approaches to tackle ranking problems like this rely on having sufficient
historical data(5694074, ; DBLP:journals/corr/ChengKHSCAACCIA16, ) to predict
user preferences. However, a limitation arises when there is minimal data
about a new content item, hindering effective recommendations. This issue,
known as the “item cold-start problem” arises especially when introducing
novel item types to a platform. To overcome the item cold-start problem and
provide effective recommendations, the Multi-Armed Bandit (MAB)
approach(thompson1933likelihood, ) is proposed. MAB balances the exploitation
of known user preferences with the exploration of new items. Contextual bandit
algorithms, a type of MAB, utilize context information, including user and
item representations, to achieve improved performance. By assuming a linear
relationship between the expected reward and context, contextual bandit
algorithms can enhance recommendations in cold-start scenarios with limited
data about newly added items(abbasi2011improved, ; chu2011contextual, ).

Contributions. In this research paper, we utilize the contextual bandit
framework to tackle the challenge of optimizing the order of widgets in order
to enhance the customer experience on our mobile shopping app. Our
contributions include:

  * •

Implementing a contextual bandit framework with diversity for dynamic widget
reordering in real-time.

  * •

Demonstrate superiority of bandit learning in a dynamic environment by
comparing the Linear UCB model against a more complex supervised XGBoost
model.

Figure 1. Example of widgets and layout on our home page: A different set of
users can be assigned to different layouts, each with its own set of widgets
that may not be mutually exclusive.

##  2\. RELATED WORK

Ever since multi-armed bandits(thompson1933likelihood, ) were introduced,
there has been substantial research and industry implementation in various
domains such as personalized recommendations(li2010contextual, ), dynamic
product pricing(misra2019dynamic, ) and portfolio optimisation(huo2017risk, ).
Multi-armed bandits are algorithms that make decisions over time by balancing
the exploration and exploitation of different options(arms) such that the
cumulative reward over time gets maximized. Contextual bandits are an
extension of the multi-armed bandit problem (pandey2007bandits,
)(NIPS2007_4b04a686, )(wang2005bandit, ) where at each round the decision
maker has access to some context related to the arms before deciding which arm
to chose. These have emerged as a powerful approach in recent years,
outperforming traditional recommender systems by effectively addressing the
challenge of cold start cases. One notable algorithm in this context is
LinUCB, which was introduced by (li2010contextual, ). It assumes a linear
payoff model, where the expected payoff or reward of an action is a linear
function of the associated context features. LinUCB has also shown good
empirical performance in (DBLP:journals/corr/KrishnamurthyAD15, ) even when
the problem was not linear. To obtain rankings from traditional MAB, we make
the assumption that each widget is regarded as an independent arm and use its
score for ranking. However, this assumption might not hold in practice, as
widgets could have interdependencies. Another approach could involve creating
individual Multi-Armed Bandits (MABs) for each ranking position. In this
method, we would treat each widget as an arm within the MAB. The MABs’
outcomes would be influenced by the previously selected arms, as displaying
the same widget multiple times would not be allowed, similar to the principles
of the Ranked Bandit Algorithm (RBA) (radlinski2008learning, ). Nevertheless,
this approach also falls short of adequately exploring the interdependencies
among widgets and requires managing multiple algorithms simultaneously. In our
approach, we have represented each widget with an embedding following the
suggestion mentioned in (saito2022off, ) to capture interdependencies among
widgets. Recently, there have been notable studies exploring various
approaches to address ranking problems, Kangas et al. investigated the use of
Evolutionary algorithms to model combinatorial bandits to tackle such
problems(kangas2022scalable, ). In another research, the integration of Deep
Neural Networks with LinUCB was explored to get a better representation of
context features (10.1145/3543873.3587684, ). However, they did not delve into
the analysis of diversity in their results.

##  3\. METHODOLOGY

Let $W$ be the set of all possible candidate widgets, and let $l$ be the total
number of slots to be shown on the page. Here, the cardinality of $W$ $\gg$
$l$. The content inside each widget is owned by different teams and ranking
within these widgets is not controlled by this algorithm. Two prominent
challenges that we faced in ranking widgets are, First, widgets are dynamic in
nature. Widgets are constantly created and removed on the platform in an
ongoing manner. We also observed that customer preferences and their
interaction with widgets change over time. Conventional recommendation systems
trained continuously tend to recommend widgets that closely resemble those
with which the user has previously engaged. This leads to no exploration and
only exploitation using users’ preferences. To mitigate these challenges, we
formulate the problem of ranking widgets as a Multi-arm Bandit (MAB) problem.

Notation |  Explanation | Notation |  Explanation
---|---|---|---
$W$ |  Set of all possible widgets | $l$ |  Total number of slots
u |  User Context | w |  Widget Context
$S$ |  item-item similarity matrix | $C$ |  Set of all customers
$\mathbb{D}_{t}$ |  Batch feedback | $\alpha$ |  Exploration parameter
$\gamma$ |  forgetting factor in LinUCB | $\theta$ |  Kernel parameter of DPP to control the relevance and diversity
Table 1. Notation used in this paper.

###  3.1. Contextual Bandit Framework

Specifically, within MAB, we use contextual bandits, where context contains
both the user’s and the widget’s features. The User context, denoted as u,
comprises a $d$-dimensional user vector $u_{v}\epsilon R^{d}$ which captures
the user preference on the platform, including user browsing, add to card
(ATC), and purchase history. Different time ranges are used while generating
embeddings to capture users’ short-term and long-term preferences. To
construct u we draw inspiration from prod2vec(vasile2016meta, ) which employs
a similar approach to generate product representation. Additionally, we
leverage a $k$-dimensional user representation $u_{svd}\epsilon R^{k}$ learned
through the Singular Value Decomposition (SVD) decomposition of the matrix
constructed using user and widget interactions. Similarly, Widget context
denoted as w, encompasses a m-dimensional widget vector $w_{v}\epsilon R^{m}$.
This vector is created using features derived from widget meta-information and
widget attributes. Furthermore, we leverage SVD decomposition to learn a
$k$-dimensional representation of each widget $w_{svd}\epsilon R^{k}$. Apart
from user and widget features, we have also taken other contextual features
such as ‘hour of the day’, ‘day of the week’(dow), ‘day of the year’(doy), and
so on. User revenue-related features are also incorporated into the model for
example ‘avg no of sessions per week’, ‘avg bucket size’ etc.

We combine u, w, and other features to form a single $z$-dimensional context
vector $\textbf{x}\epsilon R^{z}$.

Figure 2. Our Bandit Model in detail

In this paper, we have explored Linear contextual bandits particularly the
LinUCB and Linear Thompson Sampling (LinTS)(pmlr-v28-agrawal13, ). In
practice, due to resource and run-time constraints, user-widget interactions
are not processed immediately, and model parameters are updated using batch
feedback. This means that instead of updating the model after each individual
interaction, we collect interactions over a certain period, and then update
the model parameters using this aggregated feedback. Both LinUCB and LinTS
possess similar representation capabilities. While LinUCB deterministically
selects arms until new feedback is incorporated, LinTS adopts a stochastic
approach by sampling from a posterior distribution, allowing it to randomize
over actions even in the absence of updated rewards(bendada2020carousel, ).
This difference in exploration-exploitation strategies between LinUCB and
LinTS forms the basis for their comparison in this study. Now once we have the
context vector in place, CB works as follows:

  * •

In any round t, let $K_{t}$ be the number of widgets in play and we have
contextual features for each widget $x_{t,i}$.

  * •

The algorithm makes a recommendation of the current round t, based on the
parameters learned using contexts $x_{i}$ and rewards $r_{i}$ for actions
$a_{i}$ $i\epsilon[1,2,...,t-1]$ in previous rounds and the current context
$x_{t}$.

  * •

The algorithm receives the rewards of action $a_{t}$, which are based on
clicks and impressions.

In our specific setting, where we represent each widget with embedding,
widgets that share similar attributes might possess highly similar
representations. As a result, the bandit algorithm could end up selecting
similar widgets, leading to reduced diversity in the chosen widgets. This
issue arises due to the linear bandit’s focus on optimizing the expected
reward without explicitly considering diversity as an optimization criterion.
Consequently, the algorithm may tend to exploit a narrow subset of widgets
that have demonstrated favorable performance and widgets having similar
representations, limiting its exploration of diverse alternatives. In Table 2
we have demonstrated the impact of exploration coefficient $\alpha$ on
diversity metrics, as detailed in section $4.2.1$. The table showcases the
variations in these metrics corresponding to different values of $\alpha$. To
compute these metrics we have taken the top 10 recommendations generated by
the model. Although $\alpha$ plays a crucial role in the exploration-
exploitation trade-off, our results indicate that diversity metrics exhibit
relative stability across different values of this coefficient.

Note that the reward estimation function is the same for all the arms. This
allows us to effectively handle the dynamic number of arms.

Model | ILAD | ILMD
---|---|---
LinUCB ( $\alpha=0.01$ ) | 0.48024 | 0.04021
LinUCB ( $\alpha=0.05$ ) | 0.48103 | 0.03926
LinUCB ( $\alpha=0.25$ ) | 0.48079 | 0.03942
LinTS ( $\alpha=0.01$ ) | 0.48118 | 0.03959
LinTS ( $\alpha=0.05$ ) | 0.48733 | 0.04127
LinTS ( $\alpha=0.25$ ) | 0.50219 | 0.04185
Table 2. Impact of exploration coefficient $\alpha$ on diversity metrics

###  3.2. Incorporating Diversity using DPP

Focusing solely on high-relevance items might result in a repetitive selection
of similar products, disregarding the diverse preferences and interests of
individual users. The lack of content diversity can hinder the exploration of
potential appealing options, thus diminishing the overall engagement and
satisfaction of customers during their shopping journey. In this paper, we
proposed a two-stage ranking model for widgets ranking. In the first stage, we
leverage a Contextual Bandit model to generate relevance scores for the
widgets. Subsequently, we employ the Determinantal Point Process (DPP) to re-
rank the widgets based on their relevance scores and widget features. DPP
balances the relevance of widgets and their similarities. Our approach is
outlined in the Algorithm 1, which is used to rank widgets. The observed
rewards corresponding to the actions are logged and used to retrain the model
using batch feedback. To account for changes in the
environment(graepel2010web, ) and to give more importance to recent data
samples, we incorporate a forgetting factor $\gamma\epsilon[0,1]$ during model
parameter update. Algorithm 2 is adopted from (chen2018fast, ) which presents
a fast implementation of the greedy MAP inference algorithm for DPP where they
have defined diversity in the feature space of the entire subset unlike
techniques based on pairwise dissimilarities. We followed a similar approach
as highlighted in the paper to create the kernel matrix using $p_{t,1:K_{t}}$
and $X_{t,1:K_{t}}$. DPP selects a subset of items based on stopping criteria
so $Y_{t}\subseteq K_{t}$. For the final ranking, we append the remaining
widgets based on the scores obtained from the CB algorithm.

Input: Number of Rounds $T$, Number of widgets eligible per round $K_{t}$,
Dimension of feature vectors $z$, exploration parameter $\alpha$

Output: Recommended ordered widgets

1 Initialize: Set $\alpha>0$, $A\leftarrow I_{z}$, $b\leftarrow 0_{z}$; for
_$t=1,2,\ldots,T$_ do

2 $\phi_{t}\leftarrow A^{-1}_{t}b_{t}$;

3 $\mathbb{D}_{t}=\emptyset$;

4 Given a user we observe $K_{t}$ features,
$x_{t,1},x_{t,2},...x_{t,K_{t}}\epsilon\mathbb{R}^{z}$

5 for  _$k=1$ to $K_{t}$_ do

6 Calculate the upper confidence bound (UCB):
$p_{t,k}\leftarrow\phi_{t}^{T}x_{t,k}+\alpha\sqrt{x_{t,k}^{T}A_{t}^{-1}x_{t,k}}$;

7

8 end for

9 Ranked widgets $Y_{t}\leftarrow DPP(p_{t,1:K_{t}},X_{t,1:K_{t}})$

10 recommend widgets $Y_{t}$, observe rewards $R_{t}$;

11 $\mathbb{D}_{t}=\mathbb{D}_{t}\cup(X_{t},Y_{t},R_{t})$

12 Update the model using batch feedback $\mathbb{D}_{t}$

13 end for

Algorithm 1 LinUCB with diversity using DPP

Input: Positive semi-definite kernel matrix $L\in\mathbb{R}^{K_{t}\times
K_{t}}$, $stopping$ $criteria$

Output: A subset of items $Y_{t}$

1 Initialize: $c_{i}=[]$, $d^{2}_{i}=\boldsymbol{L}_{i,i}$,
$j=\text{argmax}_{i\in K_{t}}\log(d^{2}_{i})$, Set $Y_{t}=\\{j\\}$;

2 while  _stopping criteria not satisfied_ do

3 for  _$i\in K_{t}\setminus Y_{t}$_ do

4 $e_{i}=(\textbf{L}_{j,i}-(\textbf{c}_{j}\cdot\textbf{c}_{i}))/d_{j}$;

5

6 $\textbf{c}_{i}$ = [$\textbf{c}_{i}$, $e_{i}$];
$d^{2}_{i}=d^{2}_{i}-e^{2}_{i}$;

7

8 end for

9 $j=\text{argmax}_{i\in K_{t}\setminus Y_{t}}\log(d^{2}_{i})$;

10

11 $Y_{t}=Y_{t}\cup\\{j\\}$;

12

13 end while

14

Algorithm 2 DPP

Figure 3. Influence of $\theta$ on relevance (nDCG) and diversity metrics
(ILAD, ILMD).

##  4\. EXPERIMENTS

In this section, we evaluate the performance of our framework in both offline
and online evaluation. Here we have used diversity and ranking metrics to
evaluate it quantitatively. We have also demonstrated the effectiveness of our
framework through the A/B test.

###  4.1. Offline Results

In an industrial setup, off-policy evaluation is challenging. Existing
approaches require the data to be randomly logged or the current policy in
production to be similar to the test policy(gilotte2018offline, ; guo2020deep,
). However, such assumptions rarely hold true in practical scenarios, as the
data received in an industrial setup tends to be purely exploitative and
generated by statically positioned widgets for all the customers. We evaluate
our algorithm using the traditional offline method where we combine the user
and widget contexts and fed it into our framework which generates a ranked
order of widgets. We have taken the user widget interaction data for a couple
of days to train the model.

####  4.1.1. Metrics

We have used Normalized discounted cumulative gain (nDCG), Intra-list average
distance (ILAD)(zhang2008avoiding, ), and Intra-list minimal distance (ILMD)
as performance metrics. They are defined as:

The nDCG formula is given by:

$\text{nDCG}=\frac{\text{DCG}}{\text{IDCG}},$

where DCG (Discounted Cumulative Gain) is defined as:

$\text{DCG}=\sum_{i=1}^{n}\frac{2^{rel_{i}}-1}{\log_{2}(i+1)},$

and IDCG (Ideal Discounted Cumulative Gain) is the DCG score obtained with the
ideal ranking of the items.

The Diversity metrics are defined as :

$\text{ILAD}=\underset{c\epsilon C}{mean}\underset{i,j\epsilon R_{c},i\neq
j}{mean}(1-S_{i,j})$

$\text{ILMD}=\underset{c\epsilon C}{mean}\underset{i,j\epsilon R_{c},i\neq
j}{min}(1-S_{i,j})$

As we can see from figure 3 we captured the impact of varying the trade-off
parameter $\theta\epsilon[0,1]$ of DPP (chen2018fast, ) w.r.t ILAD and ILMD.
Both metrics demonstrate an almost monotonic decreasing behavior with respect
to $\theta$, while nDCG exhibits an increasing pattern. Here the higher value
of $\theta$ implies more relevance. We identify a promising range,
$0.6\leq\theta\leq 0.8$, where a desirable trade-off between relevance and
diversity can be achieved in our widget ranking case.

Figure 4. Production system architecture. Our production system consists of
(1) online inference that coordinates the frontend request and generates
ranked widgets by executing Inference Service, (2) offline model retraining in
batch mode after every time ’t’, and (3) model versioning and deployment

###  4.2. Online Results

We warm-started the model using the last 7 days of data before launching the
A/B test. We evaluated the XGBoost model alongside linUCB in a production
environment. Our results demonstrated an improvement of $\boldsymbol{0.24\%}$
in Home page clicks per user over the XGBoost model with a high statistical
significance which is a decent gain given our scale. All other guardrail
metrics such as RPU (Revenue per user), user conversion, etc. also exhibited
positive outcomes. Figure 4 shows the overall production system architecture.

##  5\. CONCLUSION AND DISCUSSION

In this paper, we modeled the personalized widgets ranking as a contextual
multi-armed bandit problem focusing on improving the overall shopping
experience of the customers. Therein, we addressed the challenges faced in
ranking widgets, we highlighted the benefits of our system, notably modeling
the widgets with features so as to cater to different types of widgets in a
single ranking purview and integrating it with DPP to achieve diversity in
ranking. We have shown offline results of our framework where we compared
LinUCB and LinTS. This framework can easily be extended to any bandit
algorithm and it can be served not just on the homepage but to any other store
pages. Future work can include a multi-objective optimization or defining a
reward in such a way that it represents an aggregate of different objectives,
we believe this can be a good research direction.

## References

  * [1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  Advances in neural information processing systems, 24, 2011.
  * [2] Shipra Agrawal and Navin Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 127–135, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.
  * [3] Walid Bendada, Guillaume Salha, and Théo Bontempelli.  Carousel personalization in music streaming apps with contextual bandits.  In Proceedings of the 14th ACM Conference on Recommender Systems, pages 420–425, 2020.
  * [4] Laming Chen, Guoxin Zhang, and Eric Zhou.  Fast greedy map inference for determinantal point process to improve recommendation diversity.  Advances in Neural Information Processing Systems, 31, 2018.
  * [5] Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, Rohan Anil, Zakaria Haque, Lichan Hong, Vihan Jain, Xiaobing Liu, and Hemal Shah.  Wide & deep learning for recommender systems.  CoRR, abs/1606.07792, 2016.
  * [6] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandits with linear payoff functions.  In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208–214. JMLR Workshop and Conference Proceedings, 2011.
  * [7] Alexandre Gilotte, Clément Calauzènes, Thomas Nedelec, Alexandre Abraham, and Simon Dollé.  Offline a/b testing for recommender systems.  In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 198–206, 2018.
  * [8] Thore Graepel, Joaquin Quinonero Candela, Thomas Borchert, and Ralf Herbrich.  Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft’s bing search engine.  Omnipress, 2010.
  * [9] Dalin Guo, Sofia Ira Ktena, Pranay Kumar Myana, Ferenc Huszar, Wenzhe Shi, Alykhan Tejani, Michael Kneier, and Sourav Das.  Deep bayesian bandits: Exploring in online personalized recommendations.  In Proceedings of the 14th ACM Conference on Recommender Systems, pages 456–461, 2020.
  * [10] Xiaoguang Huo and Feng Fu.  Risk-aware multi-armed bandit problem with application to portfolio selection.  Royal Society open science, 4(11):171377, 2017.
  * [11] Ioannis Kangas, Maud Schwoerer, and Lucas Bernardi.  Scalable user interface optimization using combinatorial bandits.  In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 3375–3379, 2022.
  * [12] Akshay Krishnamurthy, Alekh Agarwal, and Miroslav Dudík.  Efficient contextual semi-bandit learning.  CoRR, abs/1502.05890, 2015.
  * [13] John Langford and Tong Zhang.  The epoch-greedy algorithm for multi-armed bandits with side information.  In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
  * [14] Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010.
  * [15] Kanishka Misra, Eric M Schwartz, and Jacob Abernethy.  Dynamic online pricing with incomplete information using multiarmed bandit experiments.  Marketing Science, 38(2):226–252, 2019.
  * [16] Sandeep Pandey, Deepak Agarwal, Deepayan Chakrabarti, and Vanja Josifovski.  Bandits for taxonomies: A model-based approach.  In Proceedings of the 2007 SIAM international conference on data mining, pages 216–227. SIAM, 2007.
  * [17] Filip Radlinski, Robert Kleinberg, and Thorsten Joachims.  Learning diverse rankings with multi-armed bandits.  In Proceedings of the 25th international conference on Machine learning, pages 784–791, 2008.
  * [18] Steffen Rendle.  Factorization machines.  In 2010 IEEE International Conference on Data Mining, pages 995–1000, 2010.
  * [19] Yuta Saito and Thorsten Joachims.  Off-policy evaluation for large action spaces via embeddings.  arXiv preprint arXiv:2202.06317, 2022.
  * [20] Qicai Shi, Feng Xiao, Douglas Pickard, Inga Chen, and Liang Chen.  Deep neural network with linucb: A contextual bandit approach for personalized recommendation.  In Companion Proceedings of the ACM Web Conference 2023, WWW ’23 Companion, page 778–782, New York, NY, USA, 2023. Association for Computing Machinery.
  * [21] William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  Biometrika, 25(3-4):285–294, 1933.
  * [22] Flavian Vasile, Elena Smirnova, and Alexis Conneau.  Meta-prod2vec: Product embeddings using side-information for recommendation.  In Proceedings of the 10th ACM conference on recommender systems, pages 225–232, 2016.
  * [23] Chih-Chun Wang, Sanjeev R Kulkarni, and H Vincent Poor.  Bandit problems with side observations.  IEEE Transactions on Automatic Control, 50(3):338–355, 2005.
  * [24] Mi Zhang and Neil Hurley.  Avoiding monotony: improving the diversity of recommendation lists.  In Proceedings of the 2008 ACM conference on Recommender systems, pages 123–130, 2008.


# DoSSIER@COLIEE 2021: Leveraging dense retrieval and summarization-based re-
ranking for case law retrieval

Sophia Althammer  TU ViennaViennaAustria<EMAIL_ADDRESS>,
Arian Askari  Leiden UniversityLeidenNetherlands<EMAIL_ADDRESS>,  Suzan Verberne  Leiden UniversityLeidenNetherlands
<EMAIL_ADDRESS>and  Allan Hanbury  TU ViennaViennaAustria
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we present our approaches for the case law retrieval and the
legal case entailment task in the Competition on Legal Information
Extraction/Entailment (COLIEE) 2021. As first stage retrieval methods combined
with neural re-ranking methods using contextualized language models like BERT
(Devlin et al., 2019) achieved great performance improvements for information
retrieval in the web and news domain, we evaluate these methods for the legal
domain. A distinct characteristic of legal case retrieval is that the query
case and case description in the corpus tend to be long documents and
therefore exceed the input length of BERT. We address this challenge by
combining lexical and dense retrieval methods on the paragraph-level of the
cases for the first stage retrieval. Here we demonstrate that the retrieval on
the paragraph-level outperforms the retrieval on the document-level.
Furthermore the experiments suggest that dense retrieval methods outperform
lexical retrieval. For re-ranking we address the problem of long documents by
summarizing the cases and fine-tuning a BERT-based re-ranker with the
summaries. Overall, our best results were obtained with a combination of BM25
and dense passage retrieval using domain-specific embeddings.

neural IR, dense retrieval, BERT, summarization

††copyright: rightsretained††conference: COLIEE 2021 workshop: Competition on
Legal Information Extraction/Entailment ; June 21, 2021; Online††ccs:
Information systems Retrieval models and ranking††ccs: Information systems
Rank aggregation††ccs: Information systems Language models

##  1\. Introduction

In case law systems, precedent cases are a primary legal resource for the
decision of a new given case. Therefore it is a part of a lawyer’s or
paralegal’s daily work to find precedent cases which support or contradict a
new case (Turtle, 1995). With the exponentially growing amount of
electronically stored information in the legal domain (Van Opijnen and Santos,
2017), it costs legal professionals increasingly more effort to retrieve the
cases which are relevant to their case. In order to find evidence lawyers
require their search systems to find all cases which are relevant (Al-Kofahi
et al., 2001), but at the same time, legal researchers will examine up to $50$
results in practice (Russell-Rose et al., 2018) and therefore require a
precision-oriented solution.
We tackle these requirements of legal case retrieval in Task 1 of the
Competition on Legal Information Extraction/Entailment (COLIEE) 2021 by first
retrieving candidates from the whole corpus with the aim of a high recall and
then re-ranking these candidates for precision at high ranks. In Task 2 of
COLIEE 2021 it is the task to identify a paragraph of an existing case that
entails the decision of a new case (Rabelo et al., 2020) and we approach this
problem with re-ranking as well.
In news and web search, contextualized language models like BERT (Devlin et
al., 2019) brought substantial effectiveness gains to the first stage
retrieval (Reimers and Gurevych, 2019; Karpukhin et al., 2020; Lee et al.,
2019; Xiong et al., 2021; Gao et al., 2020; Hofstätter et al., 2021b) as well
as to the re-ranking stage (Nogueira and Cho, 2019; MacAvaney et al., 2019;
Hofstätter et al., 2021a; Althammer et al., 2021). We aim to transfer these
advantages also to the task of case law retrieval, however this task has
specific challenges compared to retrieval tasks in the web and news domains:
documents are written in domain specific language (Turtle, 1995), there is a
specific notion of relevance not only on document- but also on paragraph-level
(Van Opijnen and Santos, 2017) and the documents tend to be long (Van Opijnen
and Santos, 2017; Shao et al., 2020b). For example in the case law corpus from
COLIEE 2021 the documents contain on average $1274.62$ words,with minimum $1$
word and maximum $76,818$ words. This is not only the case for the candidate
documents in the retrieval collection, but also for the query cases.
As the input length of BERT is limited, we propose two different approaches
for handling the longer documents with BERT, one for first stage retrieval and
one for re-ranking. In order to achieve a high recall for the first stage
retrieval, we reason that prior cases are not only relevant on a document-
level to a query case, but that a prior case can be relevant to a query case
only based on a single paragraph which is relevant to another paragraph of the
query case (Shao et al., 2020b, a; Westermann et al., 2020). Therefore we
propose for the first stage retrieval to split up the query case and cases in
the corpus into their paragraphs and retrieve for each paragraph of the query
case relevant prior cases based on the relevance of their paragraphs. For the
document-level and paragraph-level retrieval, we evaluate both lexical
retrieval model and of a semantic retrieval model. For the lexical retrieval
model we choose BM25 (Robertson and Zaragoza, 2009) and for the dense passage
retrieval model we choose DPR (Karpukhin et al., 2020). We train the dense
passage retrieval model on the legal entailing paragraph pairs as we suggest
that the relevance of the paragraphs to each other is crucial for the
relevance on the document-level. We denote the trained DPR model with lawDPR.
When comparing the paragraph-level and document-level retrieval, we
demonstrate that the paragraph-level retrieval achieves a higher recall for
BM25 as well as for lawDPR and that lawDPR outperforms BM25 in terms of
retrieval recall. We also show that the results of the lexical and semantic
retrieval of BM25 and lawDPR complement each other and that the score
combination of both retrieval models leads to superior results.
For re-ranking the retrieved results we experiment with the approach of
summarizing the query cases and the cases in the corpus as Tran et al.
(2020b); Rossi and Kanoulas (2019) have shown that query document
summarization is valuable for case law retrieval. For this, we fine-tune
Longformer Encoder-Decoder (LED) as a state-of-the-art abstractive
summarization model (Beltagy et al., 2020) and use this for summarizing the
cases. For each query and document case, we summarize the text and interpret
the re-ranking as a binary classification problem and fine-tune BERT on
predicting whether the summarized query case is relevant to a summarized case
in the corpus or not. For Task 1 we submit 3 runs: one based on the ranking
with BM25, one with the combination of BM25 and lawDPR and one with the first
stage retrieval of BM25 and lawDPR and with re-ranking with BERT.
For the legal entailment task (Task 2) we evaluate BM25 (Robertson and
Zaragoza, 2009) and the DPR model (Karpukhin et al., 2020) trained on the
entailing paragraph pairs (’lawDPR’). Here we find that the combination of the
BM25 and DPR scores also improves the overall performance for identifying the
entailing paragraph. For Task 2 we submit 3 runs: one based on the ranking on
BM25, one based on the ranking of lawDPR and one with the combination of BM25
and lawDPR.
We make the source code available at:
https://github.com/sophiaalthammer/dossier_coliee.

##  2\. Task description

###  2.1. Task 1: The Legal Case Retrieval Task

The aim of legal case retrieval is to design systems to automatically identify
the supporting cases of a given query case, which should be noticed for
solving the query case (Rabelo et al., 2020). The task consists of reading a
new case $Q$ and selecting supporting cases $S_{1},S_{2},\dotsc,S_{n}$
(”noticed cases”) from the whole case law collection for the decision of $Q$.

###  2.2. Task 2: The Legal Case Entailment Task

In the legal case entailment task, the goal is to design a system that finds
paragraphs in a relevant case that entail the decision of a given new case
(Rabelo et al., 2020). In the Task 2 of COLIEE there is a query paragraph
given as well as the paragraphs of one legal case as candidates and the task
is to find the paragraphs from the legal case which entail the decision of the
query paragraph.

###  2.3. Training and test collection

The training and test collections for Task 1 and Task 2 contain cases from the
Federal Court of Canada case laws. For Task 1, a corpus with $4415$ legal
cases is given from which relevant cases should be retrieved for each query
case. The cases can contain as addition to the English version also a French
version. For Task 2 there are for each query paragraph the paragraphs of one
case as candidates given and one needs to identify the entailing paragraphs.
The statistics of the collections are in Table 1 including the number of
queries, the average number of relevant documents and the average length of
the queries and candidates.

Table 1. Statistics of the training and test collection for Task1 and Task2 | Task 1 | Task 2
---|---|---
| Train | Test | Train | Test
# of queries | 650 | 250 | 425 | 100
avg # of candidates | 4415 | 4415 | 32.12 | 32.18
avg # relevant candidates | 5.17 | 3.6 | 1.17 | 1.17
avg query length (words) | 690.56 | 1817.12 | 38.26 | 37.41
avg candidate length (words) | 1274.62 | 1274.62 | 102.67 | 117.91

##  3\. Methods

###  3.1. Task 1

Figure 1. Aggregation of paragraph-level retrieval to an overall ranked list
for the query document

####  3.1.1. First stage retrieval

For the lexical retrieval in the first stage retrieval we use BM25 (Robertson
and Zaragoza, 2009). When querying the index with query $q$, the BM25 model
assigns each document $d$ in the index a ranking score $s_{BM25}(d,q)$, the
higher the score, the higher the relevance of the query and the indexed
document. For semantic retrieval, we use a dense passage retrieval model
(Karpukhin et al., 2020) based on two Siamese BERT Encoders, one encodes the
query passage, the other one the candidate passage. The encoder encodes the
query and candidate passage into a vector and the dot-product between those
two vectors denotes the relevance score $s_{lawDPR}(p,q)$ between the query
$q$ and the candidate passage $p$. This dense retrieval model (lawDPR) is
trained on the entailing query-paragraph pairs of Task 2, in order to align
the vector representations of entailing paragraphs.
As the maximum input length for the dense passage retrieval model (Karpukhin
et al., 2020) is limited, we employ this model on the full text of the case by
splitting up the whole document $d$ into its paragraphs $p_{1},..,p_{m_{d}}$
and indexing each paragraph separately. When querying the paragraph-level
index, we also split up the query case $q$ into its paragraphs
$q_{1},..,q_{n_{q}}$ and retrieve for each query paragraph $q_{i}$ with
$i\in[n_{q}]$ the ranked list of paragraphs $r_{1},..,r_{n_{q}}$. The
paragraph in the ranked lists $r_{i}$ with $i\in[n_{q}]$ are reduced to the
paragraphs documents and then the ranked lists of documents are aggregated to
one ranked list of documents for the whole query case. This aggregation will
be further investigated in the next section. Equivalently we also use this
approach for retrieval with BM25 on the paragraph-level and refer to this
approach to paragraph-level retrieval.
In order to analyze the impact of the paragraph-level retrieval compared to
document-level retrieval on the retrieval effectiveness, we also conduct
document-level retrieval with BM25 and lawDPR. Here all documents in the
corpus are indexed based on their whole text and the query case is also
encoded with all its text. As the dense passage retrieval model has a limited
input length and therefore can only retrieve passages up to $512$ tokens, the
document-level retrieval for lawDPR is the retrieval based on the first $512$
tokens of the query case and the candidate case.

##### Aggregation

For the retrieval on the paragraph-level we retrieve for each paragraph of the
query document $q_{1},..,q_{n_{q}}$ a ranked list $r_{1},..,r_{n_{q}}$ of top
$N$ results. These ranked lists $r_{i}$ with $i\in[n_{q}]$ of paragraphs must
be aggregated to one overall ranked list for the whole document, this process
of aggregation is visualized in Figure 1. For the aggregation we reduce the
paragraphs per ranked list $r_{i}$ to the paragraphs’ document. As the
paragraphs are reduced to their documents it is possible that one document
occurs multiple times in the list. Within this reduction from the paragraph
$p$ to its document $d$ the scores of the retrieval model $s(p,q_{i})$ of each
paragraph $p$ in the ranked list $r_{i}$ are replaced with an integer scores
of the document $d$ $s(d,q_{i})$ according to their position: The first
document gets the score $N$, per position in the list the score decreases by
$1$ so that the last document gets the score $1$. Then we aggregate the lists
$r_{i}$ per query paragraph $q_{i}$ to one ranked list for the whole query
document by adding the integer scores for each retrieved document and ranking
by the new additive scores. The new additive score of a document $d$ for a
query $q$ is then:

$\displaystyle s(d,q)=\sum_{i=1}^{n_{q}}\sum_{d\in r_{i}}s(d,q_{i})$

We also experiment with other aggregation strategies using the similarity
scores of the retrieval model or using an interleaving approach, but find that
the aggregation with the additive integer scores $s(d,q)$ for a document $d$
and query $q$ lead to the overall best performance.

##### Combination

We find that $67\%$ of the relevant cases of Top1000 which are retrieved from
lawDPR on paragraph-level and $70\%$ of the relevant cases of Top1000 which
are retrieved from BM25 on paragraph-level are the same documents. Therefore
$23\%$ of the retrieved relevant cases from lawDPR and $30\%$ of the retrieved
relevant cases from BM25 are different, hence BM25 and lawDPR retrieve
different relevant documents. For the first stage retrieval we combine for
each document $d$ in the index the relevance scores of BM25 $s_{BM25}(d,q)$
and the relevance score for the whole document $d$ of lawDPR $s_{lawDPR}(d,q)$
from paragraph-level retrieval with BM25 and lawDPR. In order to get an
overall score of a document $d$ and a query $q$ we add the BM25 and the lawDPR
relevance scores with a scalar weighting $\alpha,\beta\in\mathbb{R}$

$\displaystyle s_{BM25+lawDPR}(d,q)=\alpha\ s_{BM25}(d,q)+\beta\
s_{lawDPR}(d,q).$

We denote the combination with BM25+lawDPR.

####  3.1.2. Re-ranking

##### Summarizer: LED

The current state of the art in abstractive summarization is Transformer
models (Lewis et al., 2019; Raffel et al., 2019). However, the input of pre-
trained available models of these architectures is limited to 1024 tokens, and
the majority of case law documents in our collection is longer than that.
Beltagy et al. (2020) proposed Longformer-Encoder-Decoder (LED), which is a
Transformer variant that supports much longer inputs. For this competition, we
evaluate the effectiveness of LED for case law retrieval.

##### BERT

For re-ranking we use BERT and fine-tune the pre-trained BERT model (BERT-
Base, uncased) with a linear combination layer stacked atop the classifier
[CLS] token on binary classification if a query summmary and a document
summary are relevant to each other or not. We represent the query as sentence
A and the document as sentence B in the BERT input:

$``[CLS]\enspace query\enspace document\enspace[SEP]\enspace candidate\enspace
document\enspace[SEP]"$

##### Cut-off value

As the task is to retrieve the relevant cases to a given query $q$, we
consider the top-k-ranked documents $d$ in the ranked list as relevant and
denote $k$ as cut-off value. We evaluate the best cut-off value $k$ depending
on the F1-score of the validation set.

###  3.2. Task 2

For identifying the entailing paragraphs $p$ to a given query paragraph $q$ we
use lexical and semantic ranking approaches in order to rank the given
candidate paragraphs $p$. In order to predict which paragraphs of the ranking
are entailing the query paragraph, we consider the top-k-ranked paragraphs,
where we denote $k$ as cut-off value. We evaluate the best cut-off value $k$
depending on the F1-score on the validation set.
In order to rank each paragraph given the query paragraph, we create per query
paragraph an index containing the given candidate paragraphs. Then we query
this index with the query paragraph and obtain the ranking for the candidate
paragraphs. We do this procedure either using BM25 or lawDPR in order to
compare both models for the legal entailment task.

##### BM25

For the lexical ranking we use BM25 (Robertson and Zaragoza, 2009).

##### lawDPR

For the semantic retrieval we use the same dense retrieval model (Karpukhin et
al., 2020) as in Task 1, which is trained on the entailing query-paragraph
pairs of the training collection for Task 2. As Task 2 is on paragraph-level
we can directly use the dense passage retrieval model without aggregating the
results as in Task 1.

##### BM25+lawDPR

We also combine the ranking of BM25 and lawDPR with the same method as for
Task 1.

##  4\. Experiment design

###  4.1. Data pre-processing

For the experiments we divide the training collections of Task 1 and Task 2
into a training and validation set. The validation sets for Task 1 and for
Task 2 contain the last 100 query cases of the training sets, respectively.
For the data pre-processing for Task 1, we remove the French versions of the
cases when reading in the cases. We divide the cases into an introductory
part, a summary, if they contain one, and their paragraphs. As we want to
distinguish the cases by their text, we remove text parts of the cases which
appear exactly the same in multiple cases, as they do not add any information
which is particular for one case. Therefore we remove introductory parts and
summaries, which appear exactly the same in more than $100$ cases from the
case text as we consider them as non-informative. The introductory parts have
an average length of $73.66$ words, the summaries have on average $227.05$
words and the paragraphs have a average length of $92.80$ words. We use the
same data pre-processing for all submitted runs.
We pre-process the data of Task 2 by reading in the paragraphs, splitting the
words at whitespaces and removing tabs. Here we also use the same data pre-
processing for all submitted runs.

###  4.2. Task 1

####  4.2.1. First stage retrieval

##### BM25

We use the BM25 implementation from
ElasticSearch111https://github.com/elastic/elasticsearch with default
parameter values $k=1.2$ and $b=0.75$.

##### lawDPR

We train the dense retrieval model with two BERT-based-uncased Siamese
Encoders on the training set and validation set of Task 2 in the same fashion
as in (Karpukhin et al., 2020). Here a pair of query and candidate paragraph
which are relevant to each other are considered as positive sample and a pair
of query and candidate paragraph which are not relevant to each other are
considered as negative sample. Different to Karpukhin et al. (2020) we sample
the negative candidate paragraphs to a query paragraph randomly from the
paragraphs which are not denoted as relevant to this query paragraph. We train
the model for $40$ epochs with a pairwise loss for the first $30$ epochs and a
list-based loss for the last $10$ epochs, in order to include the pairwise and
listwise relation of the samples in the training. We use batch size of $22$, a
maximum sequence length of $256$ and a learning rate of $2*10^{-5}$.

We index the corpus on the paragraph- and on the document-level using BM25 and
lawDPR and then query each index with the query cases. For the paragraph-level
retrieval the query is split up into its paragraphs, for each query paragraph
a ranked list of paragraphs is retrieved and aggregated to a ranked list of
documents as described in section 3. For the first stage retrieval on the
paragraph-level the introductory part and the summary are also treated as
paragraph of the document. For the document-level retrieval the documents are
indexed based on their whole text and for each query case the whole text is
taken into account.

##### BM25+lawDPR

We experiment with combining the scores of BM25 and lawDPR as described in
section 3. We take the Top1000 aggregated lists for the paragraph-level
retrieval of BM25 and lawDPR and use the weights
$[\alpha,\beta]\in\\{[1,1],[2,1],[3,1],$ $[4,1]\\}$.

####  4.2.2. Re-ranking

##### Summarizer: LED

For LED, we used the Huggingface transformers
library222https://huggingface.co/transformers/ and set the local attention
window size to 512 tokens. To limit memory use, we use gradient checkpointing
and set the input size in training to $8192$ tokens which covers more than
$86\%$ of COLIEE’18 Task 1 documents completely (the longer documents are
truncated at $8912$ tokens). We set the maximum length to generate a summary
for an unseen document as $10\%$ of the length of the original text. We use
the COLIEE’18 Task 1 data, which contains human reference summaries, for
evaluation of the summarizers333As opposed to COLIEE’19 and COLIEE’20,
COLIEE’18 contains expert-written summaries..

In COLIEE’18, the summaries are provided for all queries and more than $80\%$
of document cases. We extracted summaries like (Tran et al., 2020a), and after
removing duplicates, $6,257$ unique documents are left for which a summary is
available. Finally, we fine-tuned the LED model on the unique documents that
contains summary. We kept the other hyperparameters (optimizer, dropout,
weight decay) identical to (Beltagy et al., 2020) and set the global attention
on the first ¡s¿ token. We use the fine-tuned LED on COLIEE’18 to generate
summary for query and document cases in COLIEE’21, and provide the summaries
as the representation of cases in BERT-based re-ranking step.

##### BERT-based re-ranking

We truncate the summarized documents such that the concatenated query document
(truncated at 100 words), candidate document, and the separator tokens do not
exceed $512$ tokens. We re-rank the top-500 BM25+lawDPR results. We find $k=7$
as the optimal cut-off of the ranking for the selection of documents. We train
each model for $100$ epochs, each with $32$ batches of $16$ training pairs,
with the initial learning rate of $3*10^{-5}$, followed by a power 3
polynomial decay.

For Task 1 we submit 3 runs: one based on the paragraph-level retrieval and
ranking of BM25, the second based on the combination of paragraph-level
retrieval of BM25 and lawDPR and the third takes the retrieved candidates from
the combination of BM25 and lawDPR and re-ranks them using the summarizer and
BERT.

###  4.3. Task 2

##### BM25

We use the BM25 implementation from ElasticSearch with default parameters and
create an index for each query paragraph and its candidates.

##### lawDPR

We take the trained lawDPR model from Task 1.

##### BM25+lawDPR

We combine the scores of BM25 and lawDPR as described in scetion 3 and use the
weights $[\alpha,\beta]\in\\{[1,1],[2,1],[3,1]$
$,[4,1]\\}$. For Task 2 we submit 3 runs: one based on BM25, the second based
on lawDPR and the third with the combination of BM25 and lawDPR.

Table 2. Task 1: Recall@N for the first stage retrieval of BM25 and lawDPR on the paragraph-level and the document-level retrieval on validation set Model | Retrieval level | R@100 | R@200 | R@300 | R@500
---|---|---|---|---|---
BM25 | document-level | 0.5519 | 0.6525 | 0.6938 | 0.7715
BM25 | paragraph-level | 0.5303 | 0.6765 | 0.7469 | 0.8164
lawDPR | document-level | 0.1172 | 0.1381 | 0.1651 | 0.2466
lawDPR | paragraph-level | 0.4776 | 0.6111 | 0.6757 | 0.7735
BM25+lawDPR | paragraph-level | 0.5639 | 0.6932 | 0.7577 | 0.8193
Table 3. Task 1 validation set evaluation Run | Precision | Recall | F1-Score
---|---|---|---
BM25 (cutoff at 7) | 0.0948 | 0.0471 | 0.0629
BM25+lawDPR (cutoff at 7) | 0.0987 | 0.0471 | 0.0638
BERT re-ranking (cutoff at 7) | 0.0296 | 0.0157 | 0.0205
Table 4. Task 1 test set evaluation Run | Precision | Recall | F1-Score
---|---|---|---
BM25 (cutoff at 7) | 0.0777 | 0.1959 | 0.1113
BM25+lawDPR (cutoff at 7) | 0.0737 | 0.1788 | 0.1044
BERT re-ranking (cutoff at 7) | 0.0211 | 0.0546 | 0.0304

##  5\. Results and analysis

###  5.1. Task 1

####  5.1.1. First stage retrieval

We compare the first stage retrieval of BM25 and lawDPR on the paragraph- and
the document-level and also evaluate the combination of the scores of BM25 and
lawDPR. In the first stage retrieval it is our goal to achieve a high recall,
therefore we evaluate the recall@100, recall@200, recall@300 and recall@500
using pytrec_eval444https://github.com/cvangysel/pytrec_eval on the validation
set. The results are shown in Table 2. As described in section 4 we combine
the scores of BM25 and lawDPR and obtain a list ranked by the combination of
the BM25 and lawDPR scores. When evaluating the retrieval on the validation
set, we find that the combination with the weights $[3,1]$ leads to the best
results, therefore we only present the results for this weighting and denote
it as BM25+lawDPR.

Comparing the retrieval on paragraph- and document-level we see that the
retrieval on paragraph-level outperforms the retrieval on whole document-level
for BM25 as well as for lawDPR. This shows that our approach of tackling the
long documents for a contextualized language model with limited input length
is not only beneficial for the dense passage retrieval model, but also for the
lexical retrieval with BM25.
Furthermore we see that BM25 outperforms the first stage retrieval on
paragraph-level of lawDPR by $4-6\%$ in terms of recall@N. However when
combining the scores of BM25 and lawDPR, we see that the overall recall is the
best at all evaluated cut-off values.

####  5.1.2. Ranking

Figure 2. F1-score for Task 1 on the validation set for different cut-off
values of our runs

We evaluate the precision, recall and F1-scores for the runs we submitted at
the cut-off value of $7$ for each run as we find in out analysis in Figure 2
that the best cut-off value in terms of F1-score is $7$ for all three runs.
The evaluation results on the validation set are in Table 3 and on the test
set in Table 4.
Here we see that the overall ranking performance is improved for the
validation set of BM25+lawDPR, this approach also outperforms the re-ranking
based on the summaries. Contrary to that we find that on the test set BM25
achieves the best performance in terms of precision, recall and F1-score.
There is a difference in the evaluation scores between our evaluation and the
evaluation of the task coordinator. We use for our evaluation the off-the-
shelf pytrec_eval555https://github.com/cvangysel/pytrec_eval library and were
in contact with the task organizer, however we could not clarify the
differences between the evaluations.

Figure 3. F1-score of task 2 on the validation set for different cut-off values of our runs, BM25:$\alpha$ DPR: $\beta$ denotes the weighting factors of the BM25+lawDPR run Table 5. Task 2 validation set evaluation Run | Precision | Recall | F1-Score
---|---|---|---
BM25 (cutoff at 1) | 0.5583 | 0.6300 | 0.5719
lawDPR (cutoff at 1) | 0.5283 | 0.6000 | 0.5618
BM25+lawDPR (cutoff at 1) | 0.6333 | 0.7100 | 0.6694

###  5.2. Task 2

For Task 2 we evaluated precision, recall and F1-score on the evaluation set
for multiple cut-off values. The overall F1-score for multiple cut-off values
is visualized in Figure 3, the performance for the precision and recall of
various cut-off values is visualized in Figure 4. Figure 4 shows how the
precision decreases with an increasing cut-off value and therefore an
increasing recall. Here we also see that BM25 and lawDPR have a similar
performance, with lawDPR having a better performance with a higher cut-off
value than BM25. We also clearly see the gap between BM25 and lawDPR and the
combination of the scores of BM25 and lawDPR. We see a similar picture in
Figure 3, here the F1-score is continuously decreasing with a higher cut-off
value, therefore we select a cut-off value of $1$ for each run. We also see
that the overall performance is the best with the weight $[4,1]$ therefore we
use these weights for combining BM25 and lawDPR.
In Table 5 we can see the precision, recall and F1-score on the validation set
for BM25, lawDPR and BM25+lawDPR. Here we see that BM25 has a better
performance than lawDPR, but that both runs are outperformed by the
combination of BM25 and lawDPR. This also suggests that combining the
strengths of lexical and semantic retrieval models is beneficial for legal
paragraph entailment and that BM25 and lawDPR complement each other.
We also evaluate our three final runs on the test set, the evaluation results
can be found in Table 6. Here we find the same relations between the
evaluation results as for the validation set evaluation.

Figure 4. Precision and recall of Task 2 on the validation set for different cut-off values of our runs, BM25:$\alpha$ DPR: $\beta$ denotes the weighting factors of the BM25+lawDPR run Table 6. Task 2 test set evaluation Run | Precision | Recall | F1-Score
---|---|---|---
BM25 (cutoff at 1) | 0.6300 | 0.5953 | 0.6121
lawDPR (cutoff at 1) | 0.5600 | 0.5203 | 0.5394
BM25+lawDPR (cutoff at 1) | 0.7100 | 0.6753 | 0.6922

##  6\. Conclusion and future work

Our participation at COLIEE 2021 in Task 1 and Task 2 gave the opportunity to
explore information retrieval challenges in the legal case law retrieval and
legal entailment. Our goal is to combine traditional lexical retrieval models
with dense passage retrieval models as well as use contextualized re-ranking
models for re-ranking the results. For legal case retrieval we identify the
challenge of long documents for dense retrieval and neural re-ranking
strategies. Therefore we present, compare and evaluate two approaches for
handling the long documents:

  * •

Splitting up the documents into their paragraphs and proposing a paragraph-
level retrieval for first stage retrieval and

  * •

Generating summaries for the neural re-ranking with BERT.

We show that the paragraph-level retrieval in the first stage outperforms the
document-level retrieval and that the combination of lexical and semantic
retrieval models leads to the best results. Also for the ranking we find that
the combination of lexical and semantic models improves the overall
effectiveness of the ranking. Our experiments with re-ranking based on the
summaries of the cases seems not to improve the overall ranking effectiveness.
Furthermore we also find that the combination of lexical and semantic
retrieval methods improves the overall performance also for the passage
entailment task. This leads to the conclusion that lexical and semantic
retrieval methods have different strengths and complement each other. In
future we plan to investigate dense retrieval models with domain specific
contextualized language models like LegalBERT (Chalkidis et al., 2020) and
with different paragraph aggregation approaches.

###### Acknowledgements.

This work was supported by the EU Horizon 2020 ITN/ETN on Domain Specific
Systems for Information Extraction and Retrieval (H2020-EU.1.3.1., ID:
860721).

## References

  * (1)
  * Al-Kofahi et al. (2001) Khalid Al-Kofahi, Alex Tyrrell, Arun Vachher, and Peter Jackson. 2001.  A Machine Learning Approach to Prior Case Retrieval.  _Proceedings of the 8th International Conference on Artificial Intelligence and Law_ , 88–93.
  * Althammer et al. (2021) Sophia Althammer, Sebastian Hofstätter, and Allan Hanbury. 2021.  Cross-domain Retrieval in the Legal and Patent Domains: a Reproducibility Study. In _Advances in Information Retrieval, 43rd European Conference on IR Research, ECIR 2021_.
  * Beltagy et al. (2020) Iz Beltagy, Matthew E Peters, and Arman Cohan. 2020\.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_ (2020).
  * Chalkidis et al. (2020) Ilias Chalkidis, Manos Fergadiotis, Prodromos Malakasiotis, Nikolaos Aletras, and Ion Androutsopoulos. 2020.  LEGAL-BERT: The Muppets straight out of Law School. In _Findings of the Association for Computational Linguistics: EMNLP 2020_. Association for Computational Linguistics, Online, 2898–2904.  https://doi.org/10.18653/v1/2020.findings-emnlp.261
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. Association for Computational Linguistics, Minneapolis, Minnesota, 4171–4186.  https://doi.org/10.18653/v1/N19-1423
  * Gao et al. (2020) Luyu Gao, Zhuyun Dai, Tongfei Chen, Zhen Fan, Benjamin Van Durme, and Jamie Callan. 2020\.  Complementing Lexical Retrieval with Semantic Residual Embedding.  (4 2020).  http://arxiv.org/abs/2004.13969
  * Hofstätter et al. (2021a) Sebastian Hofstätter, Sophia Althammer, Michael Schröder, Mete Sertkan, and Allan Hanbury. 2021a.  Improving Efficient Neural Ranking Models with Cross-Architecture Knowledge Distillation.  arXiv:2010.02666 [cs.IR]
  * Hofstätter et al. (2021b) Sebastian Hofstätter, Sheng-Chieh Lin, Jheng-Hong Yang, Jimmy Lin, and Allan Hanbury. 2021b.  Efficiently Teaching an Effective Dense Retriever with Balanced Topic Aware Sampling.  arXiv:2104.06967 [cs.IR]
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020\.  Dense Passage Retrieval for Open-Domain Question Answering. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Online, 6769–6781.  https://doi.org/10.18653/v1/2020.emnlp-main.550
  * Lee et al. (2019) Kenton Lee, Ming-Wei Chang, and Kristina Toutanova. 2019\.  Latent Retrieval for Weakly Supervised Open Domain Question Answering. In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Florence, Italy, 6086–6096.  https://doi.org/10.18653/v1/P19-1612
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019\.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_ (2019).
  * MacAvaney et al. (2019) Sean MacAvaney, Andrew Yates, Arman Cohan, and Nazli Goharian. 2019.  CEDR: Contextualized embeddings for document ranking. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 1101–1104.
  * Nogueira and Cho (2019) Rodrigo Nogueira and Kyunghyun Cho. 2019.  Passage Re-ranking with BERT.  _arXiv preprint arXiv:1901.04085_ (2019).
  * Rabelo et al. (2020) Juliano Rabelo, Mi-Young Kim, Randy Goebel, Masaharu Yoshioka, Yoshinobu Kano, and Ken Satoh. 2020\.  A Summary of the COLIEE 2019 Competition. In _New Frontiers in Artificial Intelligence_ , Maki Sakamoto, Naoaki Okazaki, Koji Mineshima, and Ken Satoh (Eds.). Springer International Publishing, Cham, 34–49.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _arXiv preprint arXiv:1910.10683_ (2019).
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. Association for Computational Linguistics, Hong Kong, China, 3982–3992.  https://doi.org/10.18653/v1/D19-1410
  * Robertson and Zaragoza (2009) Stephen Robertson and Hugo Zaragoza. 2009.  The Probabilistic Relevance Framework: BM25 and Beyond.  _Found. Trends Inf. Retr._ 3, 4 (April 2009), 333–389.  https://doi.org/10.1561/1500000019
  * Rossi and Kanoulas (2019) Julien Rossi and Evangelos Kanoulas. 2019.  Legal search in case law and statute law.  _Frontiers in Artificial Intelligence and Applications_ 322, 83–92.  https://doi.org/10.3233/FAIA190309
  * Russell-Rose et al. (2018) Tony Russell-Rose, Jon Chamberlain, and Leif Azzopardi. 2018\.  Information retrieval in the workplace: A comparison of professional search practices.  _Information Processing and Management_ 54 (11 2018), 1042–1057.  Issue 6. https://doi.org/10.1016/j.ipm.2018.07.003
  * Shao et al. (2020a) Yunqiu Shao, Bulou Liu, Jiaxin Mao, Yiqun Liu, Min Zhang, and Shaoping Ma. 2020a.  THUIR@COLIEE-2020: Leveraging Semantic Understanding and Exact Matching for Legal Case Retrieval and Entailment.  _CoRR_ abs/2012.13102 (2020).  arXiv:2012.13102 https://arxiv.org/abs/2012.13102
  * Shao et al. (2020b) Yunqiu Shao, Jiaxin Mao, Yiqun Liu, Weizhi Ma, Ken Satoh, Min Zhang, and Shaoping Ma. 2020b.  BERT-PLI: Modeling Paragraph-Level Interactions for Legal Case Retrieval. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20_ , Christian Bessiere (Ed.). International Joint Conferences on Artificial Intelligence Organization, 3501–3507.  https://doi.org/10.24963/ijcai.2020/484 Main track.
  * Tran et al. (2020a) Vu Tran, Minh Le Nguyen, Satoshi Tojo, and Ken Satoh. 2020a.  Encoded summarization: summarizing documents into continuous vector space for legal case retrieval.  _Artificial Intelligence and Law_ 28, 4 (2020), 441–467.
  * Tran et al. (2020b) Vu Tran, Minh Nguyen, Satoshi Tojo, and Ken Satoh. 2020b.  Encoded summarization: summarizing documents into continuous vector space for legal case retrieval.  _Artificial Intelligence and Law_ 28 (12 2020).  https://doi.org/10.1007/s10506-020-09262-4
  * Turtle (1995) Howard Turtle. 1995\.  Text Retrieval in the Legal World.  _Artificial Intelligence and Law_ 3 (1995), 5–54.
  * Van Opijnen and Santos (2017) Marc Van Opijnen and Cristiana Santos. 2017.  On the Concept of Relevance in Legal Information Retrieval.  _Artif. Intell. Law_ 25, 1 (March 2017), 65–87.  https://doi.org/10.1007/s10506-017-9195-8
  * Westermann et al. (2020) H. Westermann, J. Šavelka, and K. Benyekhlef. 2020\.  Paragraph similarity scoring and fine-tuned BERT for legal information retrieval and entailment.. In _COLIEE 2020_.
  * Xiong et al. (2021) Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. 2021\.  Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=zeFrfgyZln