Maximal Marginal Relevance

hardPRORetrieval & SimilarityLLM 3: Applications & Evaluation

Implement Maximal Marginal Relevance (MMR) for diverse retrieval.

MMR selects documents that are both relevant to the query and diverse: $\text{MMR} = \arg\max_{d \in R \setminus S} [\lambda \cdot \text{sim}(d, q) - (1-\lambda) \cdot \max_{d_j \in S} \text{sim}(d, d_j)]$

where S is the set of already selected docs, R is the candidate set, λ balances relevance vs. diversity, and sim is cosine similarity.

Input:

Line 1: N D K lambda (num docs, dimension, num to select, lambda)
Line 2: query vector
Next N lines: document vectors

Output: Indices of K selected documents in order of selection.

Example

Input

4 2 2 0.5
1.0 0.0
1.0 0.1
0.9 0.0
0.0 1.0
0.5 0.5

Output

0 2

Reasoning

We start with an empty set $S$ of selected documents and a candidate set $R$ containing all documents.
The first document is selected based on its relevance to the query, calculated as $\text{sim}(d, q)$ , which is the cosine similarity between the document vector $d$ and the query vector $q$ . In this case, document 0 has the highest similarity to the query vector $[1.0, 0.0]$ .
For the second selection, we calculate the MMR score for each remaining document $d$ in $R \setminus S$ using the formula: $\lambda \cdot \text{sim}(d, q) - (1-\lambda) \cdot \max_{d_j \in S} \text{sim}(d, d_j)$ . With $\lambda = 0.5$ , document 2 has the highest MMR score, balancing its relevance to the query and diversity from the already selected document 0.
The selected documents are output in the order of their selection, resulting in the output: 0 2

Constraints

0 <= lambda <= 1
1 <= K <= N
Cosine similarity
If S is empty, max similarity to S = 0

More from LLM 3: Applications & Evaluation

Beam Search Decoderhard INT8 Quantization Simulatormedium Nucleus (Top-P) Samplingmedium Top-K Samplingeasy Temperature Samplingeasy

Concept primerPREVIEW

Background Knowledge

The Maximal Marginal Relevance (MMR) problem is a classic problem in the field of information retrieval and natural language processing. It involves selecting a subset of documents from a larger set of candidate documents, such that the selected documents are both relevant to a given query and diverse among themselves. The relevance of a document to a query is typically measured using a similarity metric, such as cosine similarity, which calculates the cosine of the angle between two vectors in a high-dimensional space. The diversity of a set of documents is measured by the similarity between each pair of documents in the set.

The MMR problem is often formulated as an optimization problem, where the goal is to maximize a scoring function that balances the relevance of each document to the query and the diversity of the selected documents. The scoring function is typically a weighted sum of two terms: a relevance term that measures the similarity between each document and the query, and a diversity term that measures the similarity between each document and the already selected documents. The trade-off parameter λ controls the relative importance of the relevance and diversity terms. When λ is close to 1, the algorithm prioritizes relevance over diversity, while when λ is close to 0, the algorithm prioritizes diversity over relevance.

The MMR problem has many applications in real-world information retrieval systems, such as search engines, recommender systems, and question answering systems. It is particularly useful when the goal is to retrieve a diverse set of documents that cover different aspects of a topic or query. For example, in a search engine, MMR can be used to retrieve a set of documents that cover different perspectives on a topic, such as news articles, blog posts, and academic papers.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results