K NEAREST NEIGHBOR SEARCHAPPROACH TO LEGAL PRECEDENCERETRIEVAL
Moemedi Lefoane, Tshepho Koboyatshwene, and Lakshmi Narasimhan
University of Botswana{moemedi.lefoane,tshepho.koboyatshwene,lakshmi.narashimhan}@mopipi.ub.bw

Abstract. People increasingly rely on digital technologies to store andaccess information they need. Among those are the precedence court casejudgments which form part on the law in nations that adopt common
law system. As such legal practitioners have a challenge of retrieving previous cases that can help support their arguments from the repositories
of prior cases which grow exponentially every year. This make retrievalof prior cases a challenging task. Over the years research advancements
in research communities such as Natural Language Processing, Information Retrieval, Information Extraction as well as Machine Learning
provided solution to help effectively retrieve relevant cases. We propose
Information Retrieval and Unsupervised Learning approach to the taskof supporting cases for a given query. Supporting cases are also referred
to as noticed cases: Specifically we deploy Information retrieval approach
where term frequency-inverse document frequency is used as a similarity measure between a query and candidate cases, in addition we use
k-nearest neighbor search still using term frequency-inverse document
frequency as a distance measure for this task. In our approach we firstrank documents according to their relevance to the query, we then apply
filtering to exclude lowest scoring documents from relevant cases, using
threshold value to cut off lowest scoring case judgments. Evaluation of
our results show performance of 72% recall and 62% recall on information retrieval approach and unsupervised learning approach respectively.
We however observe relatively lower scores when we compare precisionperformance scores to recall scores.
Keywords: legal Precedence Information Retrieval · Nearest Neighbor
Search · TFIDF.

1Introduction

A user (a legal practitioners working on a case) usually approach an information
retrieval system with an information need. Information need is presented in theform of a query. An example of a query is a case judgment that a user is reading
and the information need is finding similar cases that can help support arguments in cases they are working on. For this task a query is derived from fact

M. Lefoane et al.

and summary of a case of interest. The information need is finding supportingcases from a collection of candidate cases, cited cases are likely to discuss thesame issues as discussed in the query. Several approaches could be used help address the users’ information need, they range from machine learning approaches,natural language processing, information retrieval, information extraction andother. where unsupervised machine learning approaches could be deployed suchas k-means clustering, k-nearest neighbor search and others. Other solutions are
Information Retrieval approaches with term weighting models such as BM25,
term frequency-inverse document frequency (TFIDF) and others. Other researchadvancement include query expansion and formulation that aim to improve retrieval effectiveness by improving the query terms. Other approaches include
natural language processing techniques that investigate the effect of parts ofspeech tagging and how they can be applied to improve retrieval effectiveness.
In our study we investigate the use of unsupervised learning approach toprecedence retrieval, specifically we deploy K-Nearest neighbor search and TFIDF
on noticed cases retrieval. Trstenjak et al [3] investigated the possibility of applying K-Nearest Neighbor search with TFIDF for text classification by finding
nearest neighbors articles of different categories, they reported promising resultswith their approach. We follow the same approach by using K-Nearest neighboralgorithm with TFIDF, however we do not classify case judgments into different
categories but we find k-nearest neighbors as first level ranking of candidate casejudgments, we then apply filtering to help cut out less relevant candidate casejudgments.
Section 1 provided a brief introduction. The rest of the paper is organised asfollows; Section 2 outlines our proposed approach in details. Finally Section 3,4, 5 and 6 discuss evaluation measures used, results, discussion and conclusion
respectively.

2

Proposed Approach

2.1

DatasetThe dataset used was compiled by COLIEE2018 Case Law competition organizers. As outlined below the dataset was divided into 2; namely training and test
set:– Training Set:
• 285 Facts and Summaries - These are used to derive queries.
• 200 Candidate Cases for each of the 285 Queries - from these 200 candidate cases, models were developed to retrieve supporting cases from thecandidate cases. The supporting cases (also referred to as noticed cases)
were then compiled and sent to COLIEE2018 organisers for evaluation.
• Ground truths for each of the 285 cases were provided, i.e. all the supporting cases for each of the 285 facts and summaries. Using groundtruths models developed were evaluated and optimized.
– Test Set:

KNN RETRIEVAL OF LEGAL PRECEDENCE• 59 facts and summaries for the cases.
• 200 Candidate Cases for each of the 59 facts and summaries of cases(queries).
Models developed using training set were then used on the training set
to generate supporting cases runs. The runs were sent to COLIEE2018
organisers for evaluation.
2.2

Architecture of the System

Figure 1 shows the architecture of the proposed system. The system receives
summary and fact of the case and it is passed through the query generator.
Query generator derives the query from both fact and summary. The query
generator uses TFIDF scores of terms in the fact, summary as well as the 200candidate cases. Terms from fact and summary are combined and 50% of thelowest scoring terms are dropped. The remaining forms the query. The queryis then used to retrieve supporting cases from candidate cases. Before retrieval
process candidate cases are passed through the indexer which creates an index.
Once the index is created, the retriever then use it to create a ranked list of
200 candidate cases matching the query. The ranked list has the highest scoringcases at the top of the ranked list. The ranked list is passed to the filter. Thefilter either gives top 25% of the 200 candidate cases as noticed for each of thequeries. The filter can also apply the post filtering approach that computes thethreshold score that is used to drop the lowest scoring cases. The result of thefilter process is noticed cases for a given query. The noticed cases produced canbe evaluated at this point to measure retrieval effectiveness. Further details on
how the experiment were performed are provided on Section 2.3
2.3

Experimental Setup

We submitted 3 runs for Task 1, noticed cases retrieval. For all the 3 runs wecombined both fact and summary of a case, then computed TF IDF of both fact
and summary, we then drop 50% of the lowest scoring terms, the resulting terms
we used as a query for our experiments, the intuition here was to try and keep
the most informative term of the query in an attempt to avoid drifting of theresults.
For our experiments we used Terrier 4.2 [4], Terrier is a widely used Information Retrieval open source research platform for indexing, retrieval andevaluation. It is a platform that has been used successfully for ad-hoc retrieval
tasks, it is for this reason that we chose it for this task. For preprocessing steps
we performed stopword removal, we did not do stemming on the candidate cases.
For K-Nearest neighbor search we used graphlab create.
The first run was generated by deploying K-Nearest neighbor search algorithm with TFIDF and ranking candidates cases for each of the candidate cases.
we then eliminated 75% of the lowest scoring candidate cases and the remaining formed noticed cases. The second run was generated by TFIDF which also
produced a ranked list of noticed cases according to the degree of relevance, wethen applied our filtering approach which compute the threshold scores for theM. Lefoane et al.

Fig. 1. System Architecture

candidate cases to eliminate. For the filtering approach we computed an averagescore of top 5 documents closest to the query then we divided the average by 2,
the result we used as a threshold score that we used to eliminate any documentsthat scored lower than the threshold. The final run was generated in the same
way as run one, but instead of eliminating 75% of the lowest scoring candidate
cases we applied our filtering approach used in run 2.
For run 2 we used traditional IR approach and we choose the TFIDF as thedocument ranking model, we chose this model as it captures the relevance of document by matching query terms with candidate case documents with emphasison rare terms.

3

Evaluation

Test collection based evaluation as outlined by Sanderson et al [1] dates backto 1950s, it has been adopted widely in research particularly in information
retrieval, even to date it seems it is still the preferred evaluation measure. In
their Book Manning et al [2] explain the measures of interest in evaluation for
Information Retrieval. Section 3.1- 3.2 explain Recall and P recision in moredetails.
3.1

RecallRecall is defined by Manning et al [2] as the proportion of the relevant documents that are retrieved, given by the formula in Figure 2, where tp is true

KNN RETRIEVAL OF LEGAL PRECEDENCE

positive and f n is false negative. For noticed cases retrieval, tp refers to candidate cases that are correctly classified noticed cases retrieved by the system. On
the other hand f n refers to candidate cases that should be retrieved as noticed
cases but are not retrieved by the system.

Recall =tp
tp + f nFig. 2. Recall equation as described by Manning et al [2]3.2

Precision

Manning et al [2] defines further P recision as the proportion of the retrieved
documents that are relevant. The formula for Precision is given in Figure 3,
where tp is true positive and f p is false positive. For this task tp is as definedin Section 3.1. f p refers to candidate cases that are not noticed cases but areretrieved by the system as noticed cases.

P recision =tp
tp + f pFig. 3. Precision equation as described by Manning et al [2]4Results

Table 1 shows results of the runs submitted for evaluation by our team. As
explained in Section 2.3 the first run was generated using K-Nearest Neighborsearch, the second run was generated using TFIDF and the final run was generated using K-Nearest Neighbor search with post filtering approach. Table 2
on the other hand shows results for other COLIEE2018 task 1 participants. The
results shown in the two tables are overall performance results for all queries.
These results do not provide detailed information regarding individual query
performance. Smith M.R et al [5] points out the importance of performing instance level analysis, it can help identify queries that are not classified correctly.
Instance level analysis could also help explain why the queries are not classified
correctly, ultimately explaining the overall performance failure. Furthermore information on individual query performance is vital and could lead to betterconclusion and help inform direction for further research. As such instance levelM. Lefoane et al.

analysis was performed to investigate the retrieval effectiveness further, the results are shown in Figure 4 to 7. For TFIDF approach no runs were submitted
for evaluation as only 3 runs could be submitted by each team. In order to compare performance for K-Nearest neighbor search model and TFIDF IR system
under the same conditions, TFIDF system approach was used to generate 25%of Top ranking candidate cases. It was then evaluated and used to compare thetwo systems. Figure 4 shows a comparison of precision performance of 2 TFIDF
runs; one generated by giving 25% of top ranking candidate cases as noticed
cases, and the second run generated by deploying post filtering approach. By
applying post filtering approach precision consistently increase for a number ofqueries, but not for all. Figure 5 on the other hand compare recall performancefrom runs also generated by TFIDF IR approach. Consistently recall does notchange for a number of queries when post filtering approach is applied. but forsome queries post filtering approach cut of some of the supporting cases, leading
to lower recall. Figure 6 and figure 7 shows instance level analysis for runs
generated by K-Nearest neighbor search model. It reveals that post filtering approach for some queries cuts out most of the cases up to the top of the ranked
list. This lead to a lower recall score for most of the queries. However for someof the queries precision does increase. These results are discussed in further insection 5 and conclusion is drawn.

Table 1. Results for the runs submitted.
Participant ID
ModelPrecision Recall F-measure
UBIRLED-1 KNN-25%Candidate as noticed cases 0.132881 0.623211 0.219056
UBIRLED-2
TFIDF-post filtering applied
0.195511 0.720191 0.307536
UBIRLED-3
KNN-post filtering applied
0.561404 0.101749 0.172275

Table 2. Results for Other participants’ the runs submitted.
Participant ID Precision Recall F-measure
HUKB10.497436 0.308426 0.380765
HUKB20.404661 0.303657 0.346957
JNLP-r=2.5 0.546419 0.655008 0.595806
JNLP-k=10 0.676271 0.634340 0.654635
Smartlaw0.287076 0.430843 0.344565
UA0.372477 0.322734 0.345826
UA-postproc 0.348422 0.403816 0.374080
UA-smote
0.353868 0.392687 0.372268
UL
0.563798 0.302067 0.393375

KNN RETRIEVAL OF LEGAL PRECEDENCE

Fig. 4. Instance Level Precision Performance for TFIDF approach

Fig. 5. Instance Level Recall Performance for TFIDF approach

5Discussion

Results from table 1 shows that IR approach performs better than K-Nearest
neighbor search, both in terms of precision and recall. In comparison with otherparticipants’ systems shown in Table 2, our system retrieve relevant cases withhigh recall comparable to other participants. While recall scores are high low

M. Lefoane et al.

Fig. 6. Instance Level Precision Performance for K-Nearest Neighbor search

Fig. 7. Instance Level Recall Performance for K-Nearest Neighbor searchscores in precision are observed. This is suggest that for some queries our system retrieve considerably more cases that do not support a given summary andfact than supporting cases. For K-Nearest Neighbor search, employing post filtering approach to the ranked list generated (UBIRLED-1 and UBIRLED-3) anincrease in precision is observed. On the other recall score for K-Nearest Neighbor search drops considerably when filtering approach is deployed. The increasein precision does not mean good performance if recall is not taken into consideration. The low recall score suggest that while post filtering cut cases that are
not supporting a given query, it also cut out more supporting cases. For theinformation retrieval approach where we used TFIDF term weighting model, weevaluate a run that retrieves 25% of the candidate cases as noticed cases in order
to compare IR approach to Unsupervised learning approach under the same condition. Instance level analysis was then perform to investigate the performanceKNN RETRIEVAL OF LEGAL PRECEDENCE

for individual queries. Instance level analysis reveals that post filtering approach
employed consistently increase precision. On the other hand for a number ofcases recall remains the same even after post filtering is deployed on the rankedlist. For other queries it is observed that filtering approach does cut out some of
the noticed cases, leading to reduced recall values.

6Conclusion

This paper set out to investigate retrieval effectiveness of applying unsupervised
learning approach to retrieval of supporting cases to given facts and summaryof a case. Information retrieval was used to compare and find out which of thetwo approaches performs better on this task. Results of our experiments showsslightly better performance on applying information approaches over unsupervised. However the difference in performance is not sufficient enough to conclude
without further studies as reveled by instance level analysis. Our post filtering
approach learned heuristically, works for some of the queries but not all of them.
As future work boosting and Bragging Techniques should be investigated in order to find out if by giving higher weight to documents with certain features andpenalizing those without such features. The candidate cases have some structure, for instance, headnote, summary and citations. With this structure Field
based retrieval techniques should be investigated to exploit this structure. Othertechniques include query difficulty predictors.

References
1. Sanderson, M.: Test Collection Based Evaluation of Information Retrieval
Systems. Foundations and Trends in Information Retrieval, vol. 4, 247–375(2010)https://doi.org/10.1561/1500000009
2. Manning, C. D., Raghavan, P., Schtze, H.: Introduction to Information Retrieval.
Cambridge University Press, Cambridge, UK (2008)
3. Trstenjak, B., Mikac, S, Donko, D.: KNN with TF-IDF Based Framework for Text
Categorization. 24th DAAAM International Symposium on Intelligent Manufacturing and Automation, 2013, Procedia Engineering, vol. 69, pp. 1356–1364. ScienceDirect. https://doi.org/10.1016/jproeng.2014.03.129
4. Ounis, I., Amati, G., Plachouras, V., He, B., Macdonald, C., Lioma, C.: Terrier:
A High Performance and Scalable Information Retrieval Platform. Proceedings ofACM SIGIR’06 Workshop on Open Source Information Retrieval (OSIR 2006), Seattle, Washington, USA (2006). https://doi.org/10.10007/1234567890
5. Smith, M.R.,Martinez, T.,Giraud-Carrier, C.:An Instance Level Analysis of Data
Complexity. Machine Learning (2014), vol. 95, pp. 225–256. Springer.