In this work, we propose a method for document re-ranking, which exploits negative feedback represented by non-relevant documents. The concept of non-relevance is modelled through the quantum negation operator. The evaluation carried out on a standard collection shows the e ectiveness of the proposed method in both the classical Vector Space Model and a Semantic Document Space.
SDinit (di) + (1 ) sim(di; d ) (1) where SDinit (di) is the score of di in the initial rank Dinit, while sim(di; d ) is the similarity degree between the document vector di and the ideal document vector d computed by cosine similarity. The outcome of the process is a list of documents ranked according to the new scores computed using Equation 1. In our approach, documents are represented as vectors in a geometric space in which similar documents are represented close to each other. This space can be the classical Vector Space Model (VSM) or a Semantic Document Space (SDS) induced by a distributional approach. Moreover, we compare our strategy with a classical strategy based on \information subtraction". 2
To build the ideal document d we use a geometrical space where d is computed as a vector close to relevant documents and unrelated to non-relevant ones. In our space the concept of relevance is expressed in terms of similarity, while the concept of irrelevance is de ned by orthogonality (similarity equals to zero). Formally, we want to compute the vector which represents the following logical operation: d = d1+ _ d2+ _ : : : _ dn+ ^ N OT (d1 ) ^ N OT (d2 ) ^ : : : ^ N OT (dm) (2) where D+ = fdi+; i = 1 : : : ng and D = fdj ; j = 1 : : : mg are the subsets of relevant and non-relevant documents respectively.
As shown in [
Thus, it is possible to build the ideal document vector d in two steps: 1. compute the disjunction of relevant documents as the vector sum of relevant documents. Indeed, disjunction in set theory is modelled as set union, which corresponds to the vector sum in linear algebra; 2. compute the projection of the vector sum of relevant documents onto the orthogonal space de ned by the vector sum of non-relevant documents, for example using the Gram-Schmidt method. This means that the result vector captures those aspects that are common to relevant documents and are distant from non-relevant ones.
Disjunction and negation using quantum logic are thoroughly described in
[
The aim of our evaluation is twofold. We want to prove that our re-ranking
strategy based on quantum negation improves retrieval performance and
outperforms the \information subtraction" method. To perform re-ranking using
a classical \information subtraction" strategy, we assume that documents are
represented by classical bag-of-words. Given D+ and D , the computation of
the ideal document dC is based on the Rocchio [
1 jD+j i2D+
X di
1 jD j j2D
X dj
(4)
Moreover, we want to evaluate the performance of our approach when a reduced
space, likewise a Semantic Document Space, is involved. The SDS is built by
Random Indexing (RI) [
We set up a baseline system based on the BM25 multi- elds model [
The evaluation has been designed using the CLEF 2009 Ad-Hoc WSD Robust Task collection. To evaluate the performance we performed 150 runs by considering all possible combinations of the three parameters involved in our method: n (the cardinality of D+), m (the cardinality of D ) and the parameter used for the linear combination of the scores (see Equation 1). We selected di erent ranges for each parameter: n ranges in [1; 5; 10; 20; 40], m in [0; 1; 5; 10; 20; 40], while in [0:3; 0:4; 0:5; 0:6; 0:7]. The cardinality of Dinit was set to 1,000.
Identifying relevant documents is quite straightforward: we assume the top ranked documents as relevant, while identifying non-relevant ones is not trivial. We proposed two strategies to select the set (D ) of non-relevant documents, which are based on plausible heuristics rather than a theory: 1. BOTTOM, which selects the non-relevant documents from the bottom of the rank; 2. RELJUD, which relies on relevance judgements provided by CLEF organizers. This technique selects the top m ranked documents which are nonrelevant exploiting the relevance judgements. We use this strategy to \simulate" the user's explicit feedback; in other words we assume that the user selects the rst m non-relevant documents.
We evaluate each run in terms of MAP and GMAP over all the queries. Table 1 reports the results for the baseline and all three strategies (Information Subtraction, VSM and SDS ). For each strategy, positive stands for the best run when only relevant documents were involved, while BOT T OM and RELJ U D indicate the best run obtained for both strategies respectively. Improvements in percentage ( %) with respect to the baseline are reported.
The experimental results are very encouraging. Both methods (BOT T OM and RELJ U D) show improvements with respect to the baseline in all the approaches. The main outcome is that quantum negation outperforms the \information subtraction" strategy.
Genarally, BOT T OM strategy results in not signi cant improvements, and in the case of \information subtraction", the introduction of non-relevant documents results in lower performance. The blind selection of non-relevant documents produces a side e ect in \information subtraction" strategy due to the baseline n m -
M AP positive 1 0 0.6 0.4208 +1.67 Information Subtraction BOTTOM 1 1 0.6 0.4175 +0.87
RELJUD 40 40 0.7 0.5932 +43.32
SDS positive 1 0 0.5 0.4372 +5.63 BOTTOM 1 5 0.6 0.4384 +5.92 RELJUD 40 40 0.7 0.6649 +60.64 positive 1 0 0.5 0.4362 +5.39 BOTTOM 1 5 0.6 0.4367 +5.51 RELJUD 40 40 0.7 0.6646 +60.57 information loss, while the quantum negation removes from relevant documents only those \negative" aspects that belong to the non-relevant ones.
As expected, the method RELJ U D obtains very high results. In this case quantum negation obtains very high improvements with respect to the \information subtraction" strategy. This proves that quantum negation is able to take advantage of information about non-relevant documents. The best results in RELJ U D are obtained when a lot of non-relevant documents are involved, but in a real scenario this is highly improbable. We performed several runs considering only one non-relevant document and varying the numbers of those relevant. The highest MAP value for SDS is 0.4606 (GMAP=0.2056), while for V SM is 0.4588 (GMAP=0.2028), both values are obtained with ve relevant documents (these results are not reported for the sake of simplicity). Moreover, in both BOT T OM and RELJ U D di erences between SDS and V SM are not relevant.
These values support our thesis that negation expressed by quantum logic operator is able to model e ectively the concept of non-relevance, opening new perspective for those tasks where the concept of non relevance plays a key role.