🐟 markrel

Markov Chain Document Relevance — School your documents with Markov chains!

🐟 What is markrel? A fast, interpretable Python library that uses Markov chains to predict document relevance. Like a school of mackerel navigating the seas, markrel traces probabilistic paths through similarity space to find the most relevant documents.

    🐟🐟🐟
   🐟🐟🐟🐟
  🐟🐟🐟🐟🐟   ← Your documents
   🐟🐟🐟🐟      swimming through
    🐟🐟🐟       relevance space!

📖 Table of Contents

• 🌊 Overview
• ⚡ Quick Start
• 📚 Tutorial
• 🎯 Why markrel?
• 📊 Benchmarks
• 🔧 Installation
• 🎨 How It Works
• ✅ Advantages & Use Cases
• ❌ Limitations
• 🔗 Calibrating External Scorers
• 📖 API Reference
• 📄 License

🌊 Overview

markrel predicts whether a document is relevant to a query using Markov chains and similarity metrics. It's designed for:

• 🔍 Semantic search re-ranking — Filter top-k results with learned relevance
• 📧 Document classification — Sort documents by relevance to topics
• 🤖 Response selection — Pick best answers from candidate pool
• ⚡ High-throughput filtering — Process 50K+ documents/second

Key Features

⚡ Quick Start (3 Minutes)

1. Install

pip install markrel

2. Train & Predict

from markrel import MarkovRelevanceModel

# Your data: queries, documents, and relevance labels
queries = ["machine learning tutorial", "baking recipes", "neural networks"]
documents = ["intro to ML", "best chocolate cake", "deep learning guide"]
labels = [1, 0, 1]  # 1 = relevant, 0 = not relevant

# Create and train (using optimal config from benchmarks)
model = MarkovRelevanceModel(
    metrics=["euclidean"],      # Best single metric
    n_bins=35,                  # Optimized for F1
    bin_strategy="uniform"
)
model.fit(queries, documents, labels)

# Predict relevance
probs = model.predict_proba(
    ["deep learning", "pasta recipes"],
    ["neural networks", "italian cooking"]
)
print(probs)  # [0.82, 0.15]

3. Use with Modern Embeddings

from sentence_transformers import SentenceTransformer

# Load BGE-M3 (best model per benchmarks)
encoder = SentenceTransformer('BAAI/bge-m3')

# Encode your texts
query_emb = encoder.encode(["what is ML?"])
doc_emb = encoder.encode(["machine learning is..."])

# Train with embeddings (disable TF-IDF)
model = MarkovRelevanceModel(
    metrics=["euclidean"],
    use_text_vectorizer=False  # Use your embeddings
)
model.fit(query_emb, doc_emb, [1])

That's it! 🎉 You now have a relevance model trained on your data.

📚 Tutorial: Complete Walkthrough

Step 1: Prepare Your Data

Markrel needs (query, document, label) triples:

# Example: Question-Answer Relevance Dataset
queries = [
    "What is machine learning?",
    "How does photosynthesis work?",
    "Best pizza recipe?",
    "Explain neural networks",
    "Types of pasta?",
]

documents = [
    "Machine learning is a subset of AI...",
    "Photosynthesis converts sunlight into energy...",
    "Authentic Neapolitan pizza requires...",
    "Neural networks are computing systems...",
    "Popular pasta types include spaghetti...",
]

# Labels: 1 = relevant, 0 = not relevant
labels = [1, 1, 0, 1, 0]

Step 2: Choose Your Configuration

Based on our benchmarks, here are recommended configs:

# Option A: Balanced (Best F1)
model = MarkovRelevanceModel(
    metrics=["euclidean"],
    n_bins=35,
    bin_strategy="uniform"
)

# Option B: Catch Everything (Best Recall)
model = MarkovRelevanceModel(
    metrics=["euclidean"],
    n_bins=7,
    bin_strategy="uniform"
)

# Option C: Strict Filtering (Best Precision)
model = MarkovRelevanceModel(
    metrics=["cosine", "euclidean"],
    n_bins=24,
    bin_strategy="uniform"
)

Step 3: Train the Model

# Train on your data
model.fit(queries, documents, labels)

# Inspect what the model learned
print(model.summary())

Step 4: Make Predictions

# Get probability scores
probabilities = model.predict_proba(
    new_queries,
    new_documents
)

# Apply threshold (default 0.5, or optimized threshold from benchmarks)
threshold = 0.251  # F1-optimized threshold
predictions = probabilities >= threshold

# Or use built-in prediction with custom threshold
predictions = model.predict(
    new_queries,
    new_documents,
    threshold=0.251
)

Step 5: Advanced Usage with Embeddings

For best results, use modern embeddings:

from sentence_transformers import SentenceTransformer
import numpy as np

# Load encoder (BGE-M3 recommended)
encoder = SentenceTransformer('BAAI/bge-m3')

# Large-scale training
train_queries = encoder.encode(train_query_texts)
train_docs = encoder.encode(train_doc_texts)
test_queries = encoder.encode(test_query_texts)
test_docs = encoder.encode(test_doc_texts)

# Train markrel
model = MarkovRelevanceModel(
    metrics=["euclidean"],
    n_bins=35,
    use_text_vectorizer=False  # Important!
)
model.fit(train_queries, train_docs, train_labels)

# Batch prediction (fast!)
probs = model.predict_proba(test_queries, test_docs)

Complete Example: Email Classifier

from markrel import MarkovRelevanceModel
from sentence_transformers import SentenceTransformer

# Load data
emails = ["Urgent: Project deadline moved up", "Weekly team newsletter", "Invoice #1234 payment required"]
queries = ["urgent project emails", "team updates", "billing notifications"]
labels = [1, 0, 1]  # Which emails are relevant to which query

# Encode with BGE-M3
encoder = SentenceTransformer('BAAI/bge-m3')
email_emb = encoder.encode(emails)
query_emb = encoder.encode(queries)

# Train relevance classifier
model = MarkovRelevanceModel(
    metrics=["euclidean"],
    n_bins=35,
    use_text_vectorizer=False
)
model.fit(query_emb, email_emb, labels)

# Classify new emails
new_emails = encoder.encode([
    "RE: Project timeline discussion",
    "Your Amazon order has shipped",
    "URGENT: Server outage in production"
])
search_query = encoder.encode(["urgent project emails"])

relevance_scores = model.predict_proba(search_query, new_emails)
print(f"Email relevance scores: {relevance_scores}")
# Output: [0.78, 0.12, 0.91]

🎯 Why markrel?

The Problem

Traditional document relevance uses:

• Fixed thresholds: "Cosine > 0.7 = relevant" (ignores domain-specific patterns)
• Linear scoring: Assumes similarity linearly predicts relevance
• Black-box models: Can't explain why a document was selected

The Solution

Markrel uses Markov chains to learn non-linear relevance patterns:

Similarity Score → Bin Mapping → P(Relevance)

   0.95 ──→ Bin 9 ──→ P(rel)=0.92  ✓ Highly relevant
   0.75 ──→ Bin 7 ──→ P(rel)=0.68  ⚠ Maybe relevant
   0.45 ──→ Bin 4 ──→ P(rel)=0.23  ✗ Probably not
   0.15 ──→ Bin 1 ──→ P(rel)=0.05  ✗ Not relevant

Each bin learns its own probability from your training data, capturing domain-specific patterns.

📊 Benchmarks

WikiQA Question-Answer Relevance

Results on 6,165 test samples (4.8% positive class):

Embedding Model Comparison

Winner: BGE-M3 for accuracy, MiniLM for speed.

🔧 Installation

From PyPI (when published)

pip install markrel

From Source

git clone https://github.com/yourusername/markrel.git
cd markrel
pip install -e .

Development Install

pip install -e ".[dev]"
pytest tests/ -v

Dependencies

numpy >= 1.20.0
scikit-learn >= 1.0.0

Optional for embeddings:

sentence-transformers >= 2.0.0

🎨 How It Works

┌────────────────────────────────────────────────────────────────┐
│                    🐟 markrel Pipeline                          │
└────────────────────────────────────────────────────────────────┘

  📥 INPUT                              🔧 PROCESSING
  ────────                              ───────────
  
  ┌──────────┐                       ┌─────────────┐
  │  Query   │──┐                     │  Embed with │
  │  "What   │  │                     │  BGE-M3     │
  │  is ML?" │  │                     │  (1024-dim) │
  └──────────┘  │                     └─────────────┘
                │                           │
  ┌──────────┐  │                           ▼
  │ Document │──┘                     ┌─────────────┐
  │ "Machine │                        │ Similarity  │
  │ learning │                        │ Computation │
  └──────────┘                        └─────────────┘
                                             │
                                             ▼
                                       ┌─────────────┐
                                       │ 📊 Markov   │
                                       │   Chain     │
                                       │             │
                                       │ Bin 0: 5%   │
                                       │ Bin 4: 23%  │
                                       │ Bin 7: 68%  │
                                       │ Bin 9: 92%  │
                                       └─────────────┘
                                             │
                                             ▼
                                       ┌─────────────┐
                                       │ P(Relevant) │
                                       │    0.75     │
                                       └─────────────┘
                                             │
                                             ▼
                                       ┌─────────────┐
                                       │  ✅ Relevant│
                                       └─────────────┘

  📤 OUTPUT: Probability + Prediction

The Markov Chain

Unlike fixed thresholds, markrel learns a probability for each similarity bin:

Similarity:     0.0 ──→ 0.2 ──→ 0.4 ──→ 0.6 ──→ 0.8 ──→ 1.0
                 │       │       │       │       │       │
                 ▼       ▼       ▼       ▼       ▼       ▼
Bin:          [Bin0]  [Bin1]  [Bin2]  [Bin3]  [Bin4]  [Bin5]
                 │       │       │       │       │       │
P(Relevant):    0.05    0.12    0.35    0.68    0.89    0.95
                 │       │       │       │       │       │
               🚫      ⚠️      ⚠️      ✓       ✓       ✓
            Not Rel.    Maybe       Likely       Highly
                        Relevant    Relevant     Relevant

✅ Advantages & Use Cases

✅ Advantages

✅ Best Use Cases

❌ Limitations

🔗 Calibrating External Scorers (e.g. Jev)

If you're using an external relevance judge — an LLM-based reranker like Jev, a cross-encoder, or any model that outputs a probability — that probability is calibrated to its own judgment task, not to your domain's actual base rate. JevCalibrator reuses markrel's bin-based Markov chain to learn a recalibration curve, P(actually relevant | external score), fit against your own ground-truth labels:

from markrel.integrations import JevCalibrator

# jev_probs: raw P(relevant) from an external scorer, per training pair
# labels: independent ground-truth relevance labels for the same pairs
cal = JevCalibrator(n_bins=20, bin_strategy="quantile")
cal.fit(jev_probs, labels)

# Recalibrated probability for a new score
cal.predict_proba([0.83])

It can also combine the recalibrated score with a markrel embedding-based MarkovRelevanceModel using the same Bayesian odds-product logic markrel uses internally to combine its own metrics — useful as a cheap first-pass filter that only escalates borderline cases to the external scorer.

Note: the labels used to fit JevCalibrator must be independent of the scorer being calibrated (e.g. human review, click-through data). Calibrating a scorer against labels it produced itself just reproduces the scorer.

Full walkthrough, API table, and cascade example: docs/jev-calibrator.md.

📖 API Reference

MarkovRelevanceModel

from markrel import MarkovRelevanceModel

model = MarkovRelevanceModel(
    metrics=["euclidean"],      # Similarity metrics to use
    n_bins=35,                  # Number of bins (10-50)
    bin_strategy="uniform",     # "uniform" or "quantile"
    smoothing=1.0,              # Laplace smoothing
    combine_rule="bayesian",    # "bayesian" or "mean"
    use_text_vectorizer=True    # Auto-vectorize text
)

Methods:

• fit(queries, documents, labels) — Train the model
• predict_proba(queries, documents) — Get relevance probabilities [0-1]
• predict(queries, documents, threshold=0.5) — Binary predictions {0, 1}
• summary() — Model statistics
• get_metric_probabilities(metric) — Bin probabilities

📄 License

MIT License — See LICENSE for details.

🐟 About the Name

Markrel = Markov Chain + Relevance

Like a school of mackerel swimming through the ocean, markrel navigates the sea of documents, tracing probabilistic paths to find the most relevant matches. Each fish (document) follows the currents (similarity scores) toward their destination (relevance). 🐟🐟🐟

Ready to school your documents? Get started with Quick Start →

     🐟
   🐟🐟🐟
 🐟🐟🐟🐟🐟
   🐟🐟🐟
     🐟