Rocchio algorithm

The Rocchio algorithm is based on a method of

${\displaystyle {\vec {Q}}_{m}=a\,{\vec {Q}}_{o}+b\,{\frac {1}{|D_{r}|}}\sum _{{\vec {D}}_{j}\in D_{r}}{\vec {D}}_{j}-c\,{\frac {1}{|D_{nr}|}}\sum _{{\vec {D}}_{k}\in D_{nr}}{\vec {D}}_{k}}$

Variable	Value
${\displaystyle {\vec {Q}}_{m}}$	Modified Query Vector
${\displaystyle {\vec {Q}}_{o}}$	Original Query Vector
${\displaystyle {\vec {D}}_{j}}$	Related Document Vector
${\displaystyle {\vec {D}}_{k}}$	Non-Related Document Vector
${\displaystyle a}$	Original Query Weight
${\displaystyle b}$	Related Documents Weight
${\displaystyle c}$	Non-Related Documents Weight
${\displaystyle D_{r}}$	Set of Related Documents
${\displaystyle D_{nr}}$	Set of Non-Related Documents

As demonstrated in the formula, the associated weights (a, b, c) are responsible for shaping the modified vector in a direction closer, or farther away, from the original query, related documents, and non-related documents. In particular, the values for b and c should be incremented or decremented proportionally to the set of documents classified by the user. If the user decides that the modified query should not contain terms from either the original query, related documents, or non-related documents, then the corresponding weight (a, b, c) value for the category should be set to 0.

In the later part of the algorithm, the variables ${\displaystyle D_{r}}$, and ${\displaystyle D_{nr}}$ are presented to be sets of vectors containing the coordinates of related documents and non-related documents. Though ${\displaystyle D_{r}}$ and ${\displaystyle D_{nr}}$ are not vectors themselves, ${\displaystyle {\vec {D}}_{j}}$ and ${\displaystyle {\vec {D}}_{k}}$ are the vectors used to iterate through the two sets and form vector summations. These sums are normalized (divided) by the size of their respective document set (${\displaystyle D_{r}}$, ${\displaystyle D_{nr}}$).

In order to visualize the changes taking place on the modified vector, please refer to the image below.

Time complexity

Variable	Value
${\displaystyle \mathbb {D} }$	Labeled Document Set
${\displaystyle L_{ave}}$	Average Tokens Per Document
${\displaystyle \mathbb {C} }$	Class Set
${\displaystyle V}$	Vocabulary/Term Set
${\displaystyle L_{a}}$	Number of Tokens in Document
${\displaystyle M_{a}}$	Number of Types in Document

The time complexity for training and testing the algorithm are listed below and followed by the definition of each variable. Note that when in testing phase, the time complexity can be reduced to that of calculating the euclidean distance between a class centroid and the respective document. As shown by: ${\displaystyle \Theta (\vert \mathbb {C} \vert M_{a})}$.

Training = ${\displaystyle \Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )}$
Testing = ${\displaystyle \Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})}$ ^[1]

Usage

Though there are benefits to ranking documents as not-relevant, a relevant document ranking will result in more precise documents being made available to the user. Therefore, traditional values for the algorithm's weights (a, b, c) in Rocchio classification are typically around a = 1, b = 0.8, and c = 0.1. Modern information retrieval systems have moved towards eliminating the non-related documents by setting c = 0 and thus only accounting for related documents. Although not all retrieval systems have eliminated the need for non-related documents, most have limited the effects on modified query by only accounting for strongest non-related documents in the ${\displaystyle D_{nr}}$ set.

Limitations

The Rocchio algorithm often fails to classify multimodal classes and relationships. For instance, the country of

• Nearest centroid classifier, aka Rocchio classifier

References

• Relevance Feedback in Information Retrieval
• Relevance Feedback and Query Expansion
• Vector Space Classification
• Data Classification