11institutetext: Interdisciplinary Centre for Mathematical and Computational
Modelling, Univ. of Warsaw 22institutetext: Freie Universität Berlin,
Berlin33institutetext: EY - AI Labs, Bangalore

# Towards Grad-CAM Based Explainability in a Legal Text Processing Pipeline

Łukasz Górski 11 0000-0003-0871-6575
Shashishekar Ramakrishna 2233 0000-0002-2832-0415
Jędrzej M. Nowosielski 11 0000-0002-9627-3008

###### Abstract

Explainable AI (XAI) is a domain focused on providing interpretability and
explainability of a decision-making process. In the domain of law, in addition
to system and data transparency, it also requires the (legal-) decision-model
transparency and the ability to understand the model’s inner working when
arriving at the decision. This paper provides the first approaches to using a
popular image processing technique, Grad-CAM, to showcase the explainability
concept for legal texts. With the help of adapted Grad-CAM metrics, we show
the interplay between the choice of embeddings, its consideration of
contextual information, and their effect on downstream processing.

###### Keywords:

Legal Knowledge Representation Language Models Grad-CAM HeatMapsCNN

##  1 Introduction

Advancements in the domain of AI and Law have brought additional
considerations regarding models development, deployment, updating and their
interpretability. This can be seen with the advent of machine-learning-based
methods, which naturally exhibit a lower degree of explainability than
traditional knowledge-based systems. Yet, knowledge representation frameworks
that handle legal information, irrespective of their origin, should cover the
pragmatics or context around a given concept and this functionality should be
easily demonstrable.

Explainable AI (XAI), is a domain which has focused on providing
interpretability and explainability to a decision making process. In the
domain of law, interpretability and explainability are more than dealing with
information/data transparency or system transparency [1] (henceforth referred
to as ontological view). It additionally requires the (legal-) decision-model
transparency, the ability to understand the model’s inner working when
arriving at the decision (epistemic view). In this paper, we aim to present
the system’s user and architect with a set of tools that facilitate the
discovery of inputs that contribute to convolutional neural network’s (CNN’s)
output to the greatest degree, by adapting the Grad-CAM method, which
originated from the field of computer vision. We adapt this method to the
legal domain and show how it can be used to achieve a better understanding of
a given system’s state and explain how different embeddings contribute to end
result as well as to optimize this system’s inner workings. While this work is
concerned with the ontological perspective, we aim this as a stepping stone
for another related perspective, where the legally-based positions are
connected with explanation thus providing the ability to explain the decisions
to its addressee. This paper addresses mainly the technical aspects, showing
how Grad-CAMs can be applied to the legal texts, describing the text
processing pipeline - taking this as a departing point for deeper analyses in
future work. We aim to present this technical implementation as well as the
quantitative comparison metrics as the main contribution of the paper.

The paper is structured as follows. State-of-the-art is described in Section
2. Section 3 describes the methodology, which includes the metrics used for
results quantification. The architecture used for experiments is described in
Section 4. Section 5 talks about the different datasets used and the
experimental setup. The outcomes are described in Section 6. Finally, Section
7 provides a conclusion and future work.

##  2 Related Work

The feasibility of using different - contextual (e.g. BERT) and non-contextual
(e.g. word2vec) - embeddings was already studied outside the domain of law. In
[2], it was found that the usage of more sophisticated, context-aware methods
is unnecessary in the domains where labelled data and simple language are
present. As far as the area of law is concerned, the feasibility of using the
domain-specific vs. general embeddings (based on word2vec) for the
representation of Japanese legal texts was investigated, with the conclusion
that general embeddings have an upper hand [3]. The feasibility of using BERT
in the domain of law was also already put under scrutiny as well. In [4] its
generic pretrained version was used for embeddings generation and it was found
that large computational requirements may be a limiting factor for domain-
specific embedding creation. The same paper concluded that the performance of
the generic version is lower when compared with law-based non-contextual
embeddings. On the other hand, in [5], BERT versions trained on legal
judgments corpus (of 18000 documents) were used and it was found that training
on in-domain corpus does not necessarily offer better performance compared to
generic embeddings. In [6] contradictory conclusions were reached: the
system’s performance significantly improves when using pre-trained BERT on a
legal corpus. Those results suggest that introduction of XAI-based methods
might be a condition sine qua non for a proper understanding of general
language embeddings and their feasibility in the domain.

Grad-CAMs are explainability method originating from computer vision [7]. It
is a well established post-hoc explainability technique when CNNs are
concerned. Moreover, Grad-CAM method passed independent sanity checks [8].
Whilst it is mainly connected with the explanations of deep learning networks
used with image data, it has already been adapted for other areas of
application. In particular, CNN architecture for text classification was
described in [9], and there exists at least one implementation which extends
this work with Grad-CAM support for explainability [10]. Grad-CAMs were
already used in the NLP domain, for (non-legal) document retrieval [11].
Herein we build upon this work and investigate the feasibility of using this
method for the legal domain, in particular allowing for the visualisation of
context-dependency of various word embeddings. Legal language is a special
register of everyday language and deservers investigation on its own. The
evolution of legal vocabulary can be precisely traced to particular statutes
and precedential judgments, where it is refined and its boundaries are tested
[12]. Many terms have thus a particular legal meaning and efficacy and tools
that can safeguard final black-box models’ adherence to the particularities of
legal language are valuable.

The endeavours aimed at using XAI methods in the legal domain, similar to this
paper, have already been undertaken recently. In [13] an Attention Network was
used for legal decision prediction - coupling it with attention-weight-based
text highlighting of salient case text (though this approach was found to be
lacking). The possibility of explaining the BERT’s inner workings was already
investigated by other authors, and it was already subject to static as well as
dynamic analyses. An interactive tool for the visualisation of its learning
process was implemented in [14]. Machine-learning-based evaluation of context
importance was performed in [15]; therein it was found that accounting for the
content of a sentence’s context greatly improves the performance of legal
information retrieval system.

However, the results mentioned hereinbefore do not allow for direct and easily
interpretable comparison of different types of embeddings and we aim to
explore an easy plug-in solution facilitating this aim.

##  3 Methodology

We study the interplay between the choice of embeddings, its consideration of
contextual information, and its effect on downstream processing. For this
work, a pipeline for comparison was prepared, with the main module being the
embedder, classification CNN and metric-based evaluator. All the parts are
easily pluggable, allowing for extendibility and further testing of a
different combinations of modules.

The CNN used in the pipeline was trained for classification. We use two
different datasets for CNN training (as well as testing) 111Section 5.1,
provides a detailed discussion on the considered datasets:

  1. 1.

The Post-Traumatic Stress Disorder (PTSD) [16] dataset [17], where rhetorical
roles of sentences are classified.

  2. 2.

Statutory Interpretation - Identifying Particular (SIIP) dataset [15], where
the sentences are classified into four categories according to their
usefulness for a legal provision’s interpretation.

Whilst many methods have already been used for the analysis of aforementioned
datasets (including regular expressions, Naive Bayes, Logistic Regression,
SVMs [17], or Bi-LSTMs [18]), we are unaware of papers that use (explainable)
CNNs for this tasks. On the other hand, usage of said CNN should not be
treated as the main contribution of this paper, as the classification network
is treated only as an exemplary application, warranting conclusions regarding
the paper’s main contribution, i.e. the context-awareness of various
embeddings when used in the legal domain.

Further down the line, the embeddings are used to transform CNN input
sentences into vectors, with vector representation for each word in a sentence
concatenated. Herein our implementation is based on the prior work [10][9].

###  3.1 Comparison metrics

Grad-CAM heatmaps are inherently visual tools for data analysis. In computer
vision, they are commonly used for qualitative determination of input image
regions that contribute to the final prediction of the CNN. While they are an
attractive tool for a qualitative analysis of a single entity, they should be
supplemented with other tools for easy comparison of multiple embeddings [19]
and to facilitate quantitative analysis. Herein the following metrics are
introduced and adapted to the legal domain:

  1. 1.

Fraction of elements above relative threshold $t$ ($\mathcal{F}(v,t)$)

  2. 2.

Intersection over union with relative thresholds $t_{1}$ and $t_{2}$
($\mathcal{I}(v_{1},v_{2},t_{1},t_{2})$)

The first metric, $\mathcal{F}(t)$, is designed to measure the CNN network
attention spread over words present in the given input, i.e, what portion of
the input is taken into account by CNN in the case of a particular prediction.
It is defined as a number of elements in a vector that are larger than the
relative threshold $t$ multiplied by the maximum vector value divided by the
length of this vector.

The second metric, $\mathcal{I}(v_{1},v_{2},t_{1},t_{2})$, helps to compare
two predictions of two different models given the same input sentence. It
answers the question of whether two models, when given the same input
sentence, ‘pay attention’ to the same or different chunk(s) of the input
sentence. It takes as arguments two Grad-CAM heatmaps ($v_{1}$ and $v_{2}$),
binarizes them using relative thresholds ($t_{1}$ and $t_{2}$) and finally
calculates standard intersection over union. It quantifies the relative
overlap of words considered important for the prediction by each of two
models.

##  4 System Architecture

The architecture, as shown in Fig 1, is designed to implement the methodology
described in 3 and comprises four main modules, i.e.: preprocessing module,
embedding module, classification module and visualization module. The pre-
processing module uses some industry de facto standard text processing
libraries for spelling correction, sentence detection, irregular character
removal, etc. The embedding module houses a plug-in system to handle different
variants of embeddings, in particular BERT and word2vec. The classification
module houses simple 1D CNN which facilitates explainability method common in
computer vision i.e. Grad-CAM. The visualization module is used for heatmap
generation and metric computation.

Figure 1: System Architecture

The output from the pre-processing module is fed into the embeddings module.
The embeddings used are based on variants of BERT and word2vec. In addition to
the pre-trained ones, raw data from CourtListener [20] dataset was used for
training embeddings creation.

Within the frame of the classification module, the output from the embeddings
module is fed into a 1D convolutional layer followed by an average pooling
layer and fully-connected layers with dropout and softmax [9]. Although CNN
architectures stem from computer vision where an image forms the input of the
network, the use of CNN for the sequence of word vectors as an input is
reasonable. In a sentence relative positions of words convey meaning. It is
similar to an image where relative positions of pixels convey information,
with the difference being about dimensionality. Standard image is 2D while a
sentence is a 1D sequence of words, therefore we use the 1D CNN for the task
of sentence classification.

With Grad-CAM technique it is possible to produce a class activation map
(heatmap) for a given input sentence and predicted class. Each element of the
class activation map corresponds to one token and indicates its importance in
terms of the score of the particular (usually the predicted) class. The class
activation map gives information on how strongly the particular tokens present
in the input sentence influence the prediction of the CNN.

The software stack used for the development of this system was instrumented
under Anaconda 4.8.3 (with Python 3.8.3). Tensorflow v. 2.2.0 was used for CNN
instrumentation and Grad-CAMs calculations (with the code itself expanding
prior implementation available at [10]). Spacy 2.1.8 and blackstone 0.1.15
were used for CourtListener text cleaning. Various BERT implementations and
supporting codes were sourced from Huggingface libraries: transformers v.
3.1.0, tokenizers v. 0.8.1rc2, nlp v. 0.4.0. Two computing systems available
at ICM University of Warsaw were exploited for the experiments. Text cleaning
was performed using the okeanos system (Cray XC40) and main calculations were
run on rysy GPU cluster (4x Nvidia Tesla V100 32GB GPUs).

##  5 Experiments

###  5.1 Datasets

As stated in Section 3, we use two different datasets for experiments. The
PTSD dataset is from the U.S. Board of Veterans’ Appeals (BVA) from 2013
through 2017. The dataset deals with the decisions from adjudicated disability
claims by veterans for service-related post-traumatic stress disorder (PTSD)
[16]. The dataset itself is well-known and has already been studied by other
authors. It annotates a set of sentences originating from 50 decisions issued
by the Board according to their function in the decision [17] [21] [22]. The
classification consists of six elements: Finding Sentence, Evidence Sentence,
Reasoning Sentence, Legal-Rule Sentence, Citation Sentence, Other Sentence.

The SIIP dataset pertains to the United States Code 5 § 552a(a)(4) provision
and aims to annotate the judgments that are most useful for interpretation of
said provision. The seed information for annotation is collected from the
court decisions retrieved from the Caselaw access project data. The sentences
are classified into four categories according to their usefulness for the
interpretation: High Value, Certain Value, Potential Value, No Value [15].

###  5.2 Embeddings/Language Modeling

We use pre-trained models as well as we train domain-specific models for the
purpose of vector representation of texts. Many flavours of word2vec and BERT
embedders were tested. The paper does not go into any details on the
comparison of these pre-trained models (or other similar models) based on
performance. This has been addressed in several other papers [23][24][14].

For the word2vec a (slimmed down) GoogleNews model was used, with a vocabulary
of $300000$ words [25]. In addition, Law2vec embeddings were also employed,
which were trained on a large freely-available legal corpus, with 200
dimensions [26]. For BERT, bert-base-uncased model was used, a transformer
model consisting of 12 layers, 768 hidden units, 12 attention heads and 110M
parameters. In addition to that, a slimmed-down version of BERT, DistilBERT
was also tried, due to its accuracy being on the par with vanilla BERT, yet
offering better performance and smaller memory footprint.

In addition to pretrained models, we have also tried training our own word2vec
and BERT models. For this aim, a CourtListener [20] database was sourced.
However, due to the large computational requirements of BERT training, a small
subset of this dataset was chosen, consisting of 180MiB of judgments.
Moreover, while several legal projects provide access to a vast database of US
case-laws, it was found that the judgments available therein need to be
further processed, as the available textual representations usually contain
unnecessary elements, such as page numbers or underscores, that hinder their
machine processing. Our hand-written parser joined hyphenated words, removed
page numbers and artifacts that were probably introduced by OCR-ing;
furthermore, the text was split into sentences using spacy-based blackstone-
parser. In line with other authors [27], we have found it to be imperfect and
failing in segmenting the sentences that contained period-delimited legal
abbreviations (e.g. Fed. \- Federal). Thus it was supplemented with our own
manually-curated list of abbreviations. The training was performed using
DistilBERT model (for ca. 36 hours), as well as word2vec in two flavours,
200-dimensional (in line with the dimensionality of Law2Vec) and
768-dimensional (in line with BERT embeddings dimensionality).

As far as the BERT-based embeddings go, there is a number of ways in which
they can be extracted from the model. One of the ways is taking embeddings for
special CLS token, which prefixes any sentence fed into BERT; another
technique that was studied in the literature amounted to concatenating the
model’s final layer’s values. The optimal technique is dependent on the task
and the domain. Herein we have found the latter to offer better accuracy for
downstream CNN training. The features for CNN processing consisted of
tokenized sentences, together with embeddings for special BERT tokens (their
absence would cause a slight drop in accuracy as well).

##  6 Results

###  6.1 Metric-based heatmap comparison

| $\mathcal{F}(0.15)$ | $\mathcal{F}(0.3)$ | $\mathcal{F}(0.5)$
---|---|---|---
| Mean | StdDev | Mean | StdDev | Mean | StdDev
word2vec (GoogleNews) | 0.53 | 0.31 | 0.44 | 0.3 | 0.35 | 0.29
Law2vec | 0.6 | 0.3 | 0.52 | 0.32 | 0.42 | 0.33
word2vec (CourtListener, 200d) | 0.49 | 0.28 | 0.39 | 0.27 | 0.29 | 0.26
word2vec (CourtListener, 768d) | 0.48 | 0.28 | 0.38 | 0.28 | 0.29 | 0.27
BERT(bert-base-uncased) | 0.48 | 0.32 | 0.36 | 0.28 | 0.24 | 0.22
DistilBert(distilbert-base-uncased) | 0.67 | 0.27 | 0.56 | 0.27 | 0.38 | 0.24
DistilBERT(CourtListener) | 0.47 | 0.39 | 0.47 | 0.39 | 0.44 | 0.39
Table 1: Heatmap metric $\mathcal{F}$ for the PTSD dataset | $\mathcal{I}(0.15)$ | $\mathcal{I}(0.3)$ | $\mathcal{I}(0.5)$
---|---|---|---
| Mean | StdDev | Mean | StdDev | Mean | StdDev
word2vec (GoogleNews) – BERT(bert-base-uncased) | 0.49 | 0.25 | 0.41 | 0.24 | 0.3 | 0.21
Law2vec – BERT(bert-base-uncased) | 0.51 | 0.26 | 0.43 | 0.25 | 0.34 | 0.25
word2vec(CourtListener, 200d) – Law2Vec | 0.65 | 0.25 | 0.58 | 0.27 | 0.51 | 0.31
word2vec(CourtListener, 768d) – DistilBert(distilbert-base-uncased) | 0.44 | 0.23 | 0\. 35 | 0.22 | 0.26 | 0.21
Table 2: Heatmap metric $\mathcal{I}$ for the selected pairs of embeddings for the PTSD dataset | PTSD | SIIP
---|---|---
word2vec (GoogleNews) | 0.7 | 0.9
Law2vec | 0.69 | 0.85
word2vec (CourtListener, 200d) | 0.78 | 0.93
word2vec (CourtListener, 768d) | 0.79 | 0.94
BERT (bert-base-uncased) | 0.84 | 0.94
DistilBERT (distilbert-base-uncased) | 0.85 | 0.94
DistilBERT (CourtListener) | 0.42 | 0.85
Table 3: Test set accuracy. Figure 2: A sample heatmap for correct prediction
with word2vec (CourtListener,768d) embedding Figure 3: A sample heatmap for
failed prediction with word2vec (CourtListener,768d) embedding

A sample heatmap can be referenced in Fig. 2 and Fig. 3, with a colorbar
defining the mapping between the colors and values. Fig 2 clearly shows the
area of CNN’s attention, which can be quantified further down the line. This
picture shows a properly classified sentence, a statement of evidence, defined
by the PTSD dataset’s authors as a description of a piece of evidence. CNN
pays most attention to the phrase "medical records", which is in line with
PTSD’s authors’ annotation protocols, where this kind of sentence describes a
given piece of evidence (e.g. the records of testimony). We have found the
sentence in Fig. 3 to be hard to classify for ourselves and it prima facie
seemed for us to be an example of evidentiary sentence. In the case of CNN, no
distinctive activations can be spotted.

Yet, we did not perform any detailed analyses of such images. Instead, we
focus on two types of comparison using metrics defined in section 3.1. The
comparisons are designed to capture differences between different embeddings,
particularly in terms of context handling. First, for a given embedding we
calculate CNN network attention spread over words quantified by metric
$\mathcal{F}(t)$ averaged over all input sentences contained in the test set.
Then we can compare the mean fraction of words (tokens) in the input sentences
which contribute to prediction in the case of various embeddings. Criterion
deciding if a particular word contributes to the prediction is, in fact,
arbitrary and depends on class activation map (heatmap) binarization
threshold. This is why we test a few thresholds, including $0.15$ as suggested
in [7] for weakly supervised localization. Essentially high value of the
fraction $\mathcal{F}(t)$ indicates that most word vectors in input sentence
are taken into account by CNN during inference. Conversely, the low value of
the fraction $\mathcal{F}(t)$ indicates that most word vectors in the input
sentence are ignored by CNN during inference. The comparison results for the
PTSD dataset are shown in Table 1 and Table 2 (SIIP dataset was omitted for
brevity and due to the similarity with the presented PTSD dataset). The
outstanding similarity between word2vec and Law2Vec can be spotted in Table 2,
due to both of those models belonging to the same class, as exhibited by the
high value of $\mathcal{I}$ metric.

###  6.2 Grad-CAM guided context extraction

The analysis of heatmaps and metrics presented hereinbefore proves that only a
part of a given sentence contributes to a greater extent to final results. We
have hypothesized that it is possible to decrease the amount of CNN’s input
data to those important parts without compromising the final prediction. In
this respect, Grad-CAM was treated as a helpful heuristic that allows to
identify the most important words for a given CNN in its training phase. For
this experiment, the value of $\mathcal{F}$, for the threshold of $0.15$ was
used to select a percentage of the most important words from a given training
example. This in turn was used to compose a vocabulary (or white-list) of the
most important words that were encountered during the training. Further down
the line, this white-list was used during the inference and only the words
present on the list were passed as input to the CNN. Nevertheless, the number
of white-listed words allowed coherent sentences to be still passed into CNN
(for example, the PTSD sentence However, this evidence does not make it clear
and, before white-listing amounted to However, this evidence does not make it
clear and unmistakable.).

We have managed to keep accuracy up to the bar of an unmodified dataset using
this procedure (e.g. 0.7 for PTSD-word2vec(GoogleNews) and 0.85 for PTSD-
DistilBERT (distilbert-base-uncased).

##  7 Conclusion & Future Work

We presented the first approach to using a popular image processing technique,
Grad-CAMs to showcase the explainability concept for legal texts. Few
conclusions which we can be drawn from the presented methodology are:

  * •

The mean value of $\mathcal{F}(t)$ is higher in the case of DistilBERT
embedding than in the cases of word2vec and Law2vec embeddings. It suggests
that CNN trained and utilised with this embedding tends to take into account a
relatively larger chunk of input sentence while making prediction.

  * •

Described metrics and visualizations provide a peek into the complexity of
context handling aspects embedded in a language model.

  * •

It enables an user to identify and catalog attention words in a sentence type
for data optimization in downstream processing tasks.

Some issues which need further investigation are:

  * •

Training of these domain-specific models requires time and resources. Apart
from algorithmic optimization, data optimization also plays an important role.
Extension of this methodology can be used to remove tokens that do not
contribute to the final outcome of any downstream processing tasks. A
systematic analysis of the method presented in Section 6.2 is warranted.

  * •

Mapping of metrics from our methodology to standard machine learning metrics
could allow us to infer the quality of language models in a given domain (i.e.
legal domain). This allows us to measure the quality of a model when there is
not sufficient gold data which can be used for effective training of models
(inline to the concept of semi-supervised learning).

  * •

An extension of this approach could be used when validating the consistency of
context in facts. And inturn the legal argument chain which is built based on
these facts.

## Acknowledgment

This research was carried out with the support of the Interdisciplinary Centre
for Mathematical and Computational Modelling (ICM), University of Warsaw,
under grant no GR81-14.

## References

  * [1] Adrien Bibal, Michael Lognoul, Alexandre de Streel, and Benoît Frénay.  Legal requirements on explainability in machine learning.  Artificial Intelligence and Law, pages 1–21, 2020.
  * [2] Simran Arora, Avner May, Jian Zhang, and Christopher Ré.  Contextual embeddings: When are they worth it?, 2020.
  * [3] Linyuan Tang and Kyo Kageura.  An examination of the validity of general word embedding models for processing japanese legal texts.  In Proceedings of the Third Workshop on Automated Semantic Analysis of Information in Legal Texts, Montreal, QC, Canada, June 21, 2019, volume 2385 of CEUR Workshop Proceedings, 2019.
  * [4] Charles Condevaux, Sébastien Harispe, Stéphane Mussard, and Guillaume Zambrano.  Weakly supervised one-shot classification using recurrent neural networks with attention: Application to claim acceptance detection.  In JURIX, pages 23–32, 2019.
  * [5] Julien Rossi and Evangelos Kanoulas.  Legal search in case law and statute law.  In JURIX, pages 83–92, 2019.
  * [6] Emad Elwany, Dave Moore, and Gaurav Oberoi.  Bert goes to law school: Quantifying the competitive advantage of access to large legal corpora in contract understanding.  arXiv preprint arXiv:1911.00473, 2019.
  * [7] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  International Journal of Computer Vision, 128(2):336–359, Oct 2019\.
  * [8] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim.  Sanity checks for saliency maps.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, pages 9505–9515. Curran Associates, Inc., 2018.
  * [9] Yoon Kim.  Convolutional neural networks for sentence classification.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1746–1751, Doha, Qatar, October 2014. Association for Computational Linguistics.
  * [10] Grad-cam for text.  https://github.com/HaebinShin/grad-cam-text.  Accessed: 2020-08-05.
  * [11] Jaekeol Choi, Jungin Choi, and Wonjong Rhee.  Interpreting neural ranking models using grad-cam.  arXiv preprint arXiv:2005.05768, 2020.
  * [12] Edwina L Rissland, Kevin D Ashley, and Ronald Prescott Loui.  Ai and law: A fruitful synergy.  Artificial Intelligence, 150(1-2):1–15, 2003.
  * [13] L Karl Branting, Craig Pfeifer, Bradford Brown, Lisa Ferro, John Aberdeen, Brandy Weiss, Mark Pfaff, and Bill Liao.  Scalable and explainable legal prediction.  Artificial Intelligence and Law, pages 1–26, 2020.
  * [14] Benjamin Hoover, Hendrik Strobelt, and Sebastian Gehrmann.  exbert: A visual analysis tool to explore learned representations in transformers models, 2019.
  * [15] Jaromir Savelka, Huihui Xu, and Kevin D Ashley.  Improving sentence retrieval from case law for statutory interpretation.  In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Law, pages 113–122, 2019.
  * [16] Victoria Hadfield Moshiashwili.  The downfall of auer deference: Veterans law at the federal circuit in 2014., 2015.
  * [17] Vern R. Walker, Krishnan Pillaipakkamnatt, Alexandra M. Davidson, Marysa Linares, and Domenick J. Pesce.  Automatic classification of rhetorical roles for sentences: Comparing rule-based scripts with machine learning.  In Proceedings of the Third Workshop on Automated Semantic Analysis of Information in Legal Texts, Montreal, QC, Canada, June 21, 2019, volume 2385 of CEUR Workshop Proceedings, 2019.
  * [18] S. R. Ahmad, D. Harris, and I. Sahibzada.  Understanding legal documents: Classification of rhetorical role of sentences using deep learning and natural language processing.  In 2020 IEEE 14th International Conference on Semantic Computing (ICSC), pages 464–467, 2020.
  * [19] David Krakov and Dror G Feitelson.  Comparing performance heatmaps.  In Workshop on Job Scheduling Strategies for Parallel Processing, pages 42–61. Springer, 2013.
  * [20] Free Law Project.  Courtlistener, 2020.
  * [21] Vern R. Walker, Ji Hae Han, Xiang Ni, and Kaneyasu Yoseda.  Semantic types for computational legal reasoning: Propositional connectives and sentence roles in the veterans’ claims dataset.  ICAIL ’17, page 217–226, New York, NY, USA, 2017. Association for Computing Machinery.
  * [22] Jaromír Savelka, Vern R. Walker, Matthias Grabmair, and Kevin D. Ashley.  Sentence boundary detection in adjudicatory decisions in the united states.  2017\.
  * [23] Louis Martin, Benjamin Muller, Pedro Javier Ortiz Suárez, Yoann Dupont, Laurent Romary, Éric de la Clergerie, Djamé Seddah, and Benoît Sagot.  CamemBERT: a tasty French language model.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7203–7219, Online, July 2020. Association for Computational Linguistics.
  * [24] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter, 2019.
  * [25] Word2vec-slim.  https://github.com/eyaler/word2vec-slim.  Accessed: 2020-09-21.
  * [26] Law2vec: Legal word embeddings.  https://archive.org/details/Law2Vec.  Accessed: 2020-09-21.
  * [27] Euirim Choi, Gillian Brassil, Katie Keller, Jessica Ouyang, and Kate Wang.  Bankruptcy map: A system for searching and analyzing us bankruptcy cases at scale.


# Infostop: Scalable stop-location detection in multi-user mobility data.

Ulf Aslak<EMAIL_ADDRESS>Centre for Social Data Science, University of
Copenhagen, DK-1353 København K  DTU Compute, Technical University of Denmark,
DK-2800 Kgs. Lyngby  Laura Alessandretti  Centre for Social Data Science,
University of Copenhagen, DK-1353 København K  DTU Compute, Technical
University of Denmark, DK-2800 Kgs. Lyngby

###### Abstract

Data-driven research in mobility has prospered in recent years, providing
solutions to real-world challenges including forecasting epidemics and
planning transportation. These advancements were facilitated by computational
tools enabling the analysis of large-scale data-sets of digital traces. One of
the challenges when pre-processing spatial trajectories is the so-called _stop
location detection_ , that entails the reduction of raw time series to
sequences of destinations where an individual was stationary. The most widely
adopted solution was proposed by Hariharan and Toyama (2004) and involves
filtering out non-stationary measurements, then applying agglomerative
clustering on the stationary points. The state-of-the-art method, however,
suffers of two limitations: (i) frequently visited places located very close
(such as adjacent buildings) are likely to be merged into a unique location,
due to inherent measurement noise, (ii) traces for multiple users can not be
analysed simultaneously, thus the definition of destination is not shared
across users. In this paper, we describe the Infostop algorithm for stop
location detection that overcomes the limitations of the state-of-the-art
solution by leveraging the flow-based network community detection algorithm
Infomap. We test Infostop for a population of $\sim 1000$ individuals with
highly overlapping mobility. We show that the size of locations detected by
Infostop saturates for increasing number of users and that time complexity
grows slower than for previous solutions. We demonstrate that Infostop can be
used to easily infer social meetings. Finally, we provide an open-source
implementation of Infostop, written in Python and C++, that has a simple API
and can be used both for labeling time-ordered coordinate sequences (GPS or
otherwise), and unordered sets of spatial points.

††preprint: APS/123-QED

##  I Introduction

Understanding human mobility is paramount to tackle real-world challenges,
from containing epidemics to modelling transportation Barbosa  _et al._
(2018). Since the end of the $19th$ century, studies on individual and
collective human movements were carried out in a broad range of
disciplinesBarbosa  _et al._ (2018). Until recently, these analyses relied on
data collected from census, surveys and self-reported travel diaries, which
suffered from limitations including limited resolution, small sample sizes and
reporting biases Barbosa  _et al._ (2018). In the last decade, the
introduction and diffusion of mobile phone devices and other positioning
technologies have renewed the interest of the scientific community for human
mobility. Today, trajectories can be inferred from sources including mobile
phone call logs, location based social networks information, and data
collected from GPS devices Barbosa  _et al._ (2018). Using data collected by
electronics, media and telecommunication companies Blondel  _et al._ (2012) or
by running large-scale experimentsStopczynski  _et al._ (2014), scientists can
base their studies on large datasets collecting the positions of millions of
individuals over months and years, at the resolution of meters and seconds.
These novel datasets offer incredible new possibilities, but also call for
novel tools.

One of the key challenges related to the pre-processing of digital traces is
translating raw sequences of spatial coordinates into comprehensible data.
Typically, raw data is a stream of records (id, lat, lon,t), where id is the
identifier of a phone or other positioning object, and lat and lon
characterize its position in space at time t. Due to inherent measurement
noise, lat and lon can fluctuate even when the sensor is perfectly still. In
this format, the data is far from being simply understood. In fact, we think
of human trajectories as sequences of _trips_ between destinations and _stays_
at destinations. For example, Alice was at home today from $12am$ to $7:30am$,
she then went to the office, where she stayed from $8:00am$ to $5pm$, and then
went back home, where she has been from $5:30pm$ until $11:59pm$.
Understanding individual trajectory as sequences of _stays_ and _trips_ is the
first step necessary to compute relevant metrics that characterize mobility
behaviour, including the total distance an individual has travelled, the
radius of gyration, or the number of unique locations visited Barbosa  _et
al._ (2018).

Several solutions were proposed to transform streams of spatio-temporal
records into _stays_ and _trips_ sequences Gong  _et al._ (2015); Cao  _et
al._ (2010); Montoliu and Gatica-Perez (2010); Do and Gatica-Perez (2013); Wan
and Lin (2013); Zhao  _et al._ (2015). To date, the most adopted solution is
the ‘Lachesis Project’ developed by Hariharan and Toyama (2004) Hariharan and
Toyama (2004). The algorithm is designed to process one individual trace at
the time and it is based on a two-steps procedure. (i) First, it identifies
_stays_ as periods when an individual does not stray further than a maximum
distance $r_{1}$ for a minimum duration $t_{min}$, where $r_{1}$ and $t_{min}$
are parameters. Each stay is described as a tuple ($start$, $end$, $lat$,
$lon$), such that an individual was stationary between $start$ and $end$ at
the location identified by latitude and longitude $(lat,lon)$. (ii) Then, it
uses spatial clustering, with parameter $r_{2}$, to cluster the coordinates
$(lat,lon)$ of all stays, in order to identify _destinations_. This step
attaches a label to each of the _stays_ identified in the previous step. For
example, if Alice has two _stays_ , one in the morning and one in the evening,
that are located closer than $r_{2}$ from each other, they will be identified
as two stays in the same destination (see Hariharan and Toyama (2004) for more
details). In the most widely used formulation of the algorithm, scientists use
the DBSCAN clustering algorithm Ester  _et al._ (1996) to perform step (ii)
Pappalardo (2019).

The state-of-the-art solution based on DBSCAN suffers of two major
limitations. First, if an individual frequently stops at two separate
locations that are near each other (e.g. adjacent buildings on a campus),
location measurements from all visits should fall into two separate clusters,
but due to sampling noise they may overlap. In fact, clustering algorithms
that operate in euclidean space, such as DBSCAN Ester  _et al._ (1996) or
other agglomerative clustering methods are not well suited for this problem,
as clusters that overlap tend to get merged. Second, although it would be
possible, in principle, to use DBSCAN to cluster stays of multiple users,
DBSCAN is not suitable for multi-user traces, especially when individuals
share many destinations. This is again due to the fact that DBSCAN aggregates
areas dense in locations into single large locations.

In order to overcome the aforementioned limitations, we introduce the Infostop
algorithm for stop-location detection, described in section II. Infostop is a
two-step algorithm: the first step corresponds to step (i) of the Hariharan
and Toyama algorithm, the second step leverages the Infomap clustering
algorithm for networks to allow for the the detection of overlapping clusters
and provide fast and scalable multi-user stop-location detection.

In section III, we show that Infostop allows the identification of compact
locations for large dataset of individuals with largely overlapping
destinations (see Fig. 1 and 2), and, in this respect, it performs better than
state-of-the-art methods (see Fig. 4). We find that multi-user solutions are
comparable to individual-user solutions (see Fig. 3). We demonstrate that
Infostop has lower time complexity than the state-of-the-art (see Fig. 5). We
show that Infostop can be used to identify social contacts. In section IV, we
present a fast and flexible open-source implementation of Infostop available
in Python.

##  II The Infostop Algorithm

Infostop detects stop-locations from raw sequences of spatio-temporal data.
Like the method in Hariharan and Toyama (2004), Infostop works in two-steps.
First, it identifies _stays_ , and then _destinations_.

The algorithm takes the following input.

Data. A collection of sequences of records. Each sequence $T_{u}$ describes
the movement of a different individual $u$, and consists of $N_{u}$ records
$[(t_{u,i},x_{u,i},y_{u,i})]$, where $t_{u,i}$ is time, $x_{u,i}$ and
$y_{u,i}$ are coordinates in a two-dimensional space. Note that sequences are
ordered by time and each of them can have a different length.

Parameters.

  * •

$r_{1}$, the maximum roaming distance allowed for two points within the same
stay.

  * •

$t_{min}$, the minimum duration of a stay.

  * •

$t_{max}$, the maximum time difference between two consecutive records for
them to be considered within the same stay.

  * •

$r_{2}$, the typical distance between two stays in the same destination.

The algorithm works in two steps. In step (i), Infostop identifies _stays_ and
_trips_ , for each of the trajectories in the collection $T_{u}$, and assigns
to each record a label in {trip, stay}. Here, Infostop follows closely the
method developed by Hariharan and Toyama (2004). For more details on the
implementation of step (i), the reader can refer to the code in
111https://github.com/ulfaslak/infostop/blob/master/cpputils/main.cpp.

In step (ii), points are clustered using Infomap. First, we build a network,
where nodes correspond to _stays_ (as identified by step (i)), and a link
exists between two nodes if they are located at distance smaller than $r_{2}$.
Note that we include in the network _stays_ deriving from all the individual
trajectories. Then, we find communities of nodes using the Infomap algorithm
Rosvall  _et al._ (2009). These communities identify _destinations_ , in a
definition that is shared across individuals. For more details on the
implementation of step (ii), the reader can refer to the code
in222https://github.com/ulfaslak/infostop/blob/master/infostop/utils.py.

Thus, for each sequence of records $T_{u}$ in the input, Infostop returns a
sequence of labels with corresponding length. Records identified as trips are
assigned label $l_{u,i}=-1$, while records that are identified as stays are
assigned a positive integer, identifying the corresponding _destination_.

Figure 1: Infostop identifies compact locations in dense areas. Heatmap
showing the density of points at DTU University Campus. Polygons represent the
_destinations_ identified by Infostop.  Figure 2: Example of locations
detected with Infostop. A sample of labeled locations from an anonymous user
on a university campus. Only the median of each stay is shown. It is apparent
that many of the clusters are either very near or even overlap to some degree.

##  III Results

We test the algorithm on the trajectories of $\sim 1000$ students at the
Technical University of Denmark that were part of the same study program and
thus have largely overlapping mobility trajectories Stopczynski  _et al._
(2014). Data was collected as part of an experiment that took place between
September $2013$ and September $2015$. Participants’ position over time was
estimated from a combination GPS and WiFi information, resulting in samples
every $1-2$ minutes. The location estimation error was below $50$ m in $95\%$
of the cases.

First, we test the accuracy of the multi-user version of Infostop, by
comparing the labels obtained by runnning stop-detection for each user
separately vs for all users simultaneously. We find that the median value of
the adjusted rand index Steinley (2004) between the two solutions is equal to
one, revealing that the single-user and multi-user solutions are almost
identical (see Fig. 3). Then, we assess the quality of the Infostop solution,
by measuring the size of the largest destination (maximum distance between any
two points with the same destination label) as a function of the number of
users included in the dataset. We find that, for a choice of $r_{2}=20m$, the
quantity saturate at $\sim 100m$, while the solution of DBSCAN, run with the
same distance parameter, diverges. Then, we measure the time it takes to run
step (ii) of the stop-location detection algorithm using Infomap or DBSCAN on
the same machine. We use the Python wrapper for Infomap by Daniel Edler, Anton
Eriksson and Martin Rosvall 333https://mapequation.github.io/infomap/python/,
and the the scikit-learn Python implementation Pedregosa  _et al._ (2011) of
DBSCAN with parameters n_jobs=1, metric=haversine, leaf_size=40,
algorithm=ball_tree. We find that Infomap runs faster compared to DBSCAN (see
Fig. 5).

Finally, we use the outcome of the algorithm to identify social contacts
between individuals. Since Infostop identifies shared destinations across
users, it makes it fast to identify situations when users spent simultaneously
time in the same destination. We find that the number of such instances, after
removing meetings occurring in the DTU campus, correlates positively with the
number of calls and sms exchanged by two individuals (see Fig. 6).

Figure 3: Similarity of the single-user vs multi-user solution. The
distribution of the adjusted rand score across individuals for the single-user
vs the multi-user solution of Infostop. The rand score assesses the similarity
of two partitions (it is equal to one for identical solutions and to zero in
the random case). Results are shown for parameters $r1=20m$, $r2=20m$,
$t_{min}=10min$, $t_{max}=24h$. Figure 4: Destinations identified by infostop
are compact. The size of the largest destination identified by Infostop (blue
line) and the DBSCAN state-of-the-art algorithm (orange line) for increasing
number of users in the dataset. Results are shown for parameters $r1=20m$,
$r2=20m$, $t_{min}=10min$, $t_{max}=24h$, and using one month of data
(22555616 records). Errorbars are computed across 30 different instances (by
selecting different sets of users).

Figure 5: Infostop is faster than the state-of-the-art solution. The time in
seconds to run Infostop (blue line) and DBSCAN (orange line) on the same
machine for increasing number of points in the dataset. Results are shown for
parameters $r1=20m$, $r2=20m$, $t_{min}=10min$, $t_{max}=24h$, and using one
month of data (22555616 records). Results are shown for the multi-user
solution (top) and the single-user solution (bottom). Figure 6: Infostop
allows to identify social meetings. The median number of meetings outside
campus, or situations where users spent more than $10$ minutes simultaneously
in the same destination vs the number of mobile phone interactions, by sms
(orange line) and calls (blue line). Results are aggregated over logarithmic
bins.

##  IV Open Source Implementation

We developed an implementation of Infostop in C++ and Python. The code is
open-sorce, it is wrapped in Python, and can be installed using pip. The
package is located at
https://github.com/ulfaslak/infostop.

The Infostop package implements two models as separate classes.

  1. 1.

Infostop: Infer stop-location labels from mobility traces. An instance of the
class is initialised using the parameters $r_{1}$, $t_{min}$, $t_{max}$,
$r_{2}$ described in Section II. The main method of the class is fit_predict,
which takes as input a collection of trajectories and returns the label
associated to each record. The method works in multiple steps: (a) Temporal
downsampling: detect stationary points and store the median coordinates of
each of them. (b) Spatial downsampling: remove duplicate coordinates,
optionally with prior downsampling to total lower number of points to be
clustered. (c) Using a ball tree algorithm, identify stationary events that
are closer than $r_{2}$ and (d) constructs a network of stationary events
(where a link exists between two nodes if the are closer than ${r_{2}}$), and
cluster the network with the Infomap algorithm. (e) Reverse spatial
downsampling. (f) Reverse temporal downsampling: assign a label to each stay
using the partition returned by Infomap, and map labels back onto the input
sequence. Non-stationary points are assigned label -1, stationary ones are
assigned a positive integer corresponding to a _destination_.

  2. 2.

SpatialInfostop: Cluster a collection of points using Infomap. An instance of
the class is initialised with the parameter $r2$ described in Section II. The
main method of the class is fit_predict, which allows to cluster a collection
of spatial points. The method entails points (b-e) described above.

The package, furthermore, contains postprocessing utilities, that allow users
to inspect various aspects of their solution, among these a visualization
component that can visualize recovered destinations as convex hulls on top of
a map, optionally with stay-points scattered or heatmapped (see Fig. 1).

Our implementation of Infostop is highly flexible. The default distance metric
is the haversine distance, thus expecting the input location measurements to
be $lat,lon$ coordinates. However, the user can specify another distance
function. As such, Infostop can be used as a general clustering algorithm in
any space that allows distance measurement between points. The input data can
be either in the form of one or multiple sequences of records, thus allowing
usage for both single-user or multi-user datasets. Input sequences can include
the timestamp associated to each record or not. Thus, it allows to use data
sampled evenly or unevenly in time.

Infostop is very performant. The temporal downsampling step, which entails
iterating over the entire input sequence and computing running medians, is
implemented in a C++ submodule for speed. Moreover, Infomap is itself a C++
library. Further speedups can be achieved by specifying a
min_spacial_resolution, i.e. a lower bound on the spatial resolution. These
speedups alone make multi-user stop-detection at the scale presented here
feasible.

##  V Conclusion

We have developed Infostop, an algorithm for stop-location detection that
overcomes some of the limitations of the state-of-the-art stop-location
detection algorithms, including that (i) frequently visited places located
very close are likely to be merged into a unique location, due to inherent
measurement noise, (ii) traces for multiple users can not be analysed
simultaneously. We have shown that Infostop allows to identify shared stop-
locations across a large population of individuals sharing several common
locations. The outcome of the algorithm is more desirable than the output
obtained using previous solutions, since locations maintain compact size. We
showed that Infostop can be used to easily identify social contacts, or
occasions when individuals spent simultaneously time in the same location.
Furthermore, we have developed a fast implementation in C++ and Python, that
is available open-source. The current implementation is highly flexible and
faster, to our knowledge, than other open-source stop-location detection
algorithms implementations.

## References

  * Barbosa  _et al._ (2018) H. Barbosa, M. Barthelemy, G. Ghoshal, C. R. James, M. Lenormand, T. Louail, R. Menezes, J. J. Ramasco, F. Simini, and M. Tomasini, Physics Reports 734, 1 (2018).
  * Blondel  _et al._ (2012) V. D. Blondel, M. Esch, C. Chan, F. Clérot, P. Deville, E. Huens, F. Morlot, Z. Smoreda, and C. Ziemlicki, arXiv preprint arXiv:1210.0137 (2012).
  * Stopczynski  _et al._ (2014) A. Stopczynski, V. Sekara, P. Sapiezynski, A. Cuttone, M. M. Madsen, J. E. Larsen, and S. Lehmann, PloS one 9, e95978 (2014).
  * Gong  _et al._ (2015) L. Gong, H. Sato, T. Yamamoto, T. Miwa, and T. Morikawa, Journal of Modern Transportation 23, 202 (2015).
  * Cao  _et al._ (2010) X. Cao, G. Cong, and C. S. Jensen, Proc. VLDB Endow. 3, 1009 (2010).
  * Montoliu and Gatica-Perez (2010) R. Montoliu and D. Gatica-Perez, in  _Proceedings of the 9th International Conference on Mobile and Ubiquitous Multimedia_ (ACM, 2010) p. 12.
  * Do and Gatica-Perez (2013) T. M. T. Do and D. Gatica-Perez, IEEE Transactions on Mobile Computing 13, 638 (2013).
  * Wan and Lin (2013) N. Wan and G. Lin, Computers, Environment and Urban Systems 39, 63 (2013).
  * Zhao  _et al._ (2015) F. Zhao, A. Ghorpade, F. C. Pereira, C. Zegras, and M. Ben-Akiva, Transportation research procedia 11, 218 (2015).
  * Hariharan and Toyama (2004) R. Hariharan and K. Toyama, in  _International Conference on Geographic Information Science_ (Springer, 2004) pp. 106–124.
  * Ester  _et al._ (1996) M. Ester, H.-P. Kriegel, J. Sander, X. Xu, _et al._ , in  _Kdd_ , Vol. 96 (1996) pp. 226–231.
  * Pappalardo (2019) L. Pappalardo, arXiv preprint arXiv:1907.07062 (2019).
  * Note (1) https://github.com/ulfaslak/infostop/blob/master/cpputils/main.cpp.
  * Rosvall  _et al._ (2009) M. Rosvall, D. Axelsson, and C. T. Bergstrom, The European Physical Journal Special Topics 178, 13 (2009).
  * Note (2) https://github.com/ulfaslak/infostop/blob/master/infostop/utils.py.
  * Steinley (2004) D. Steinley, Psychological methods 9, 386 (2004).
  * Note (3) https://mapequation.github.io/infomap/python/.
  * Pedregosa  _et al._ (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Journal of Machine Learning Research 12, 2825 (2011).