Rocchio Algorithm
The Rocchio algorithm is a classic relevance feedback technique rooted in the Vector Space Model (VSM). It computes an optimized query vector by mathematically adjusting the original query vector based on known relevant and non-relevant document vectors. By maximizing the separation between relevant and non-relevant clusters in a multi-dimensional term space, the Rocchio algorithm significantly improves precision and recall in text retrieval and information filtering systems.
HOW-TO IMPLEMENT & CONFIGURE
- Python 3.10+ runtime environment
- NumPy for high-performance vector and matrix operations
- SciPy for sparse matrix representations (CSR format)
- Scikit-learn for TF-IDF vectorization and cosine similarity calculations
Architectural Setup & Environment Initialization
Initialize the virtual environment, install the requisite numerical and machine learning packages, and construct the sparse vector space representation for your corpus using TF-IDF weighting.
import numpy as np
from scipy.sparse import csr_matrix
from sklearn.feature_extraction.text import TfidfVectorizer
# Sample corpus initialization
corpus = [
"machine learning algorithms for predictive maintenance",
"deep learning and neural networks for computer vision",
"information retrieval and vector space models",
"database indexing and query optimization techniques"
]
vectorizer = TfidfVectorizer(sublinear_tf=True, norm='l2')
X = vectorizer.fit_transform(corpus)
print(f"Corpus matrix shape: {X.shape}")Core Algorithm / Protocol Logic Implementation
Implement the core Rocchio update formula: Q_m = alpha * Q_0 + (beta / |D_r|) * sum(D_r) – (gamma / |D_nr|) * sum(D_nr). Ensure sparse matrix handling to prevent memory exhaustion on high-dimensional vocabularies.
def rochio_feedback(query_vector, relevant_indices, non_relevant_indices, X, alpha=1.0, beta=0.75, gamma=0.15):
"""
Computes the updated Rocchio query vector.
query_vector: 1D numpy array or sparse row vector representing Q_0
relevant_indices: list/array of indices for relevant documents (D_r)
non_relevant_indices: list/array of indices for non-relevant documents (D_nr)
X: Sparse matrix of the corpus document vectors
"""
# Convert query to dense or keep sparse depending on operations
if hasattr(query_vector, "toarray"):
q0 = query_vector.toarray().flatten()
else:
q0 = np.array(query_vector).flatten()
# Calculate centroid of relevant documents
if len(relevant_indices) > 0:
d_r = X[relevant_indices].toarray()
centroid_relevant = np.mean(d_r, axis=0)
else:
centroid_relevant = np.zeros_like(q0)
# Calculate centroid of non-relevant documents
if len(non_relevant_indices) > 0:
d_nr = X[non_relevant_indices].toarray()
centroid_non_relevant = np.mean(d_nr, axis=0)
else:
centroid_non_relevant = np.zeros_like(q0)
# Apply Rocchio equation
q_m = (alpha * q0) + (beta * centroid_relevant) - (gamma * centroid_non_relevant)
# Zero out negative weights if strict positive vector space is required
q_m = np.maximum(q_m, 0)
return q_mVerification, Profiling & Unit Testing
Write a validation routine to ensure that the updated query vector shifts closer to relevant document clusters and further from non-relevant document clusters using cosine similarity.
from sklearn.metrics.pairwise import cosine_similarity
# Define initial query
initial_query_text = ["machine learning"]
Q_0 = vectorizer.transform(initial_query_text)
# Simulate user feedback: Doc 0 is relevant, Doc 3 is non-relevant
rel_idx = [0]
non_rel_idx = [3]
Q_m = rochio_feedback(Q_0, rel_idx, non_rel_idx, X)
# Compute similarity shift
sim_before = cosine_similarity(Q_0, X)[0]
sim_after = cosine_similarity(Q_m.reshape(1, -1), X)[0]
print("Cosine Similarities Before Rocchio:", sim_before)
print(
"Cosine Similarities After Rocchio: ", sim_after)Production Hardening & Common Failure Modes
Address negative coordinate drift, manage vocabulary drift, and ensure numerical stability when handling empty feedback sets or massive sparse matrices in production environments.
def production_rochio_guardrails(q_m, max_magnitude=10.0):
# Guard against NaN or Inf values resulting from division by zero
if not np.isfinite(q_m).all():
raise ValueError("Rocchio computation yielded non-finite values (NaN/Inf).")
# L2 Normalization to prevent magnitude explosion across multiple iterations
norm = np.linalg.norm(q_m)
if norm > 0:
q_m = q_m / norm
return q_mMathematical Formulation
The Rocchio algorithm operates by defining an optimal query Q_m in the vector space model. Given an initial query vector Q_0, a set of relevant documents D_r, and a set of non-relevant documents D_nr, the modified query is calculated as: Q_m = alpha * Q_0 + (beta / |D_r|) * sum(D_r) – (gamma / |D_nr|) * sum(D_nr). Typical heuristic parameter settings established through empirical evaluation are alpha = 1.0, beta = 0.75, and gamma = 0.15. These parameters balance the influence of the original user intent against positive reinforcement from relevant feedback and dampening penalties from non-relevant feedback.
Algorithmic Behavior & Vector Space Dynamics
In high-dimensional term spaces, queries often suffer from vocabulary mismatch and suboptimal weighting. Rocchio feedback expands the original query by introducing terms that co-occur frequently within the relevant document cluster while downweighting terms associated with the non-relevant cluster. Because negative weights can violate distance metric assumptions in certain vector space implementations, negative terms are typically truncated to zero using a ramp function max(0, weight), ensuring that the modified query remains strictly within the positive quadrant of the vector space.
Production Considerations & Scalability
Deploying Rocchio at scale requires careful handling of sparse matrix arithmetic. Converting dense arrays directly from large collections can trigger Out-Of-Memory (OOM) errors. Systems must leverage Compressed Sparse Row (CSR) or Compressed Sparse Column (CSC) data structures. Furthermore, iterative query expansion can lead to query drift if non-relevant documents dominate the feedback loop, causing the query vector to wander into unrelated semantic neighborhoods. Implementing strict L2 normalization and capping the maximum number of feedback iterations mitigates this risk.
📚 STANDARDS & ACADEMIC RFC CITATIONS
- Rocchio, J. J. (1971). Relevance feedback in information retrieval. The Smart Retrieval System: Experiments in Automatic Document Processing, 313-323.
- Salton, G., & McGill, M. J. (1983). Introduction to Modern Information Retrieval. McGraw-Hill.
- Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press.
