# Evaluation of Diversification Techniques for Legal Information Retrieval +
## 2 Legal Document Ranking Using Diversification
### Diversification Heuristics  
Diversification methods usually retrieve a set of documents based on their relevance scores and then re-rank the documents so that the top-ranked documents are diversified to cover more query subtopics. Since the problem of finding an optimum set of diversified documents is NP-hard, a greedy algorithm is often used to iteratively select the diversified set \(S\). Let \(N\) be the document set, \(u,v\in N\), \(r(q,u)\) the relevance of \(u\) to the query \(q\), \(d(u,v)\) the distance of \(u\) and \(v\), \(S\subseteq N\) with \(|S|=k\) the number of documents to be collected and \(\lambda\in[0..1]\) a parameter used for setting the trade-off between relevance and diversity. In this paper, we focus on the following representative diversification methods:  
* MMR: Maximal marginal relevance [3], a greedy method to combine query relevance and information novelty, iteratively constructs the result set \(S\) by selecting documents that maximize the following objective function: \[f_{MMR}(u,q)=(1-\lambda)\;\;r(u,q)+\lambda\;\sum_{v\in S}d(u,v)\] (5) MMR incrementally computes the standard relevance-ranked list when the parameter \(\lambda=0\) and computes a maximal diversity ranking among the documents in \(N\) when \(\lambda=1\). For intermediate values of \(\lambda\in[0..1]\), a linear combination of both criteria is optimized. In MMR Algorithm 1, the set \(S\) is initialized with the document that has the highest relevance to the query. Since the selection of the first element has a high impact on the quality of the result, MMR often fails to achieve optimum results. * Max-sum: The Max-sum diversification objective function [4] aims at maximizing the sum of the relevance and diversity in the final result set. This is achieved by a greedy approximation, Algorithm 2, that selects a pair of documents that maximizes Equation (6) in each iteration. \[f_{MAXSUM}(u,v,q)=(1-\lambda)\ (r(u,q)+r(v,q))+2\lambda\ d(u,v)\] (6) where \((u,v)\) is a pair of documents, since this objective considers document pairs for insertion. When \(|S|\) is odd, in the final phase of the algorithm, an arbitrary element in \(N\) is chosen to be inserted in the result set \(S\). Max-sum Algorithm 2, at each step, examines the pairwise distances of the candidate items \(N\) and selects the pair with the maximum pairwise distance, to insert into the set of diverse items \(S\). ```
0: Set of candidate results N, size of diverse set k
0: Set of diverse results \(S\subseteq N,|S|=k\) \(S=\emptyset\) for\(i=1\rightarrow\lfloor\frac{k}{2}\rfloor\)do  Find \((u,v)=argmax_{x,y\in N}(f_{MAXSUM}(x,y,q))\) \(\triangleright\) Select pair of docs that maximize Equation (6)  Set \(S=S\cup\{u,v\}\)  Set \(N=N\setminus\{u,v\}\) endfor if\(k\) is odd then \(S=S\cup\{i\},N_{i}\in N\) \(\triangleright\) If \(k\) is odd add an arbitrary document to \(S\) endif
```  
**Algorithm 2** Produce diverse set of results with Max-sum. * Max-min: The Max-min diversification objective function [4] aims at maximizing the minimum relevance and dissimilarity of the selected set. This is achieved by a greedy approximation, Algorithm 3, that initially selects a pair of documents that maximize Equation (7) and then in each iteration selects the document that maximizes Equation (8): \[f_{MAXMIN}(u,v,q)=(1-\lambda)\ (r(u,q)+r(v,q))+\lambda\ d(u,v)\] (7) \[f_{MAXMIN}(u,q)=\ \min_{v\in S}d(u,v)\] (8) Max-min Algorithm 3, at each step, it finds, for each candidate document, its closest document belonging to \(S\) and calculates their pairwise distance \(d_{MIN}\). The candidate document that has the maximum distance \(d_{MIN}\) is inserted into \(S\). * Mono-objective: Mono-objective [4] combines the relevance and the similarity values into a single value for each document. It is defined as: \[f_{MONO}(u,q)=r(u,q)+\frac{\lambda}{|N|-1}\ \sum_{v\in N}d(u,v)\] (9) Algorithm 4 approximates the Mono-objective. The algorithm, at the initialization step, calculates a distance score for each candidate document.