A Quantum Query Expansion Approach for Session Search ^†

Abstract

Recently, Quantum Theory (QT) has been employed to advance the theory of Information Retrieval (IR). Various analogies between QT and IR have been established. Among them, a typical one is applying the idea of photon polarization in IR tasks, e.g., for document ranking and query expansion. In this paper, we aim to further extend this work by constructing a new superposed state of each document in the information need space, based on which we can incorporate the quantum interference idea in query expansion. We then apply the new quantum query expansion model to session search, which is a typical Web search task. Empirical evaluation on the large-scale Clueweb12 dataset has shown that the proposed model is effective in the session search tasks, demonstrating the potential of developing novel and effective IR models based on intuitions and formalisms of QT.

1. Introduction

Exploring the use of intuitions, analogies and formalisms of Quantum Theory (QT) in the field of Information Retrieval (IR) has recently become an emerging interdisciplinary research area. van Rijsbergen (2004) proposed employing quantum theory (QT) as a theoretical formalism for modeling IR tasks, and showed that major IR models (logical, probabilistic and vector) can be subsumed by the single mathematical formalism in Hilbert vector spaces (which can be a complex space) [1]. Following van Rijsbergen’s pioneering work, many subsequent IR methods [2,3,4] have been proposed. The main inspiration is rooted in considering QT as a sound unified framework for manipulating vector spaces and probability. The QT formalism was applied in contextual IR in [5] to model context-sensitive probability distributions and observables. Piwowarski et al. [2] proposed that queries and documents can be modeled as density operators and subspaces, respectively. Zuccon and Azzopardi proposed a Quantum Probability Ranking Principle (QPRP) [6] to capture the inter-document dependencies as a form of “quantum interference”. Inspired by the Photon Polarization (PP) experiment in quantum physics, Zhao et al. [3] proposed a novel document re-ranking approach, and Zhang et al. [7] further proposed a query expansion model.

In this paper, we will continue with this line of research [3,7] based on the analogy of photon polarization and IR. The photon polarization [8,9] is one of the key experiments that support the explanation of quantum measurement. Briefly speaking, after a couple of polarization filters (of different polarization directions) are inserted between a light source (which generates the photons) and a screen, the amount and probability of photons that finally reach the screen can be well explained by quantum measurement instead of classical measurement [8].

This inspires us to design an analogy of photon polarization in IR. As shown in Figure 1, one can view documents as photons, and the retrieval process as measuring the probability of each document that can pass through a query filter (as polarization filter). Then, the measured probability can be regarded as the estimated probability of relevance for the document with respect to the query [3]. The photon polarization experiment usually inserts an additional filter between the original filter and the photon receiver (i.e., a screen). This is similar to query expansion, where after the first-round retrieval by the original query, an expanded or modified query that aims at a better reflection of the user’s information needs and is usually derived from the top ranked documents, can be constructed and used for the second-round retrieval [7]. Query expansion has been a widely used technique to improve document retrieval performance.

We further develop a novel Quantum interference based Query Expansion (QQE) model. In the proposed model, we assume that a document is expressed in a two-dimensional information need space, whose dimensions represent the explicit user query and the concepts that the user omits from its formulation, i.e., implicit or hidden, which we consider orthogonal. Quantum mechanics allows a physical system to be in multiple exclusive possible states simultaneously, which means it is in a superposed state [10]. In Information Retrieval, we can model the document as a superposed state of explicit and implicit information need aspects. Upon assessing its relevance, the document superposed state originates quantum interference effects, effectively capturing the interactions between the two dimensions. The incorporation of the quantum interference effect is a fundamental difference, compared with the previous quantum fusion approach to query expansion [7] and the PP-inspired document ranking model [3]. We also implement this new quantum query expansion model in the session search task, where the explicit information need is expressed by the user’s currently input query, and the implicit/hidden information need can be estimated or simulated by the historical interactions in search sessions.

Extensive experiments have been conducted on TREC [11] Session Tracks 2013 and 2014 with the Clueweb12 (Category B) collection [12]. The evaluation results show that the proposed QQE model significantly outperforms various state-of-the-art query expansion models. Moreover, our empirical study also reveals that introducing the quantum interference term in the quantum query expansion approach can consistently improve the retrieval performance.

2. Related Work

van Rijsbergen (2004) proposed employing quantum theory (QT) formalism for modeling IR tasks [1] by showing that major IR models (logical, probabilistic and vector) can be subsumed by the single mathematical formalism in Hilbert vector spaces. Specifically, QT provides a geometrical vector representation for information objects (e.g., documents, queries, multimedia objects) in a complex Hilbert space, allowing measurement of observables as relevance status of information objects, probability calculation via the trace formula in Gleason’s Theory [13], logical reasoning through lattice structures, and modeling the change of states via evolution operators [1].

Following van Rijsbergen’s pioneering work [1], a series of QT-based IR approaches have been proposed, which can be classified into three main themes [14]: Spaces: geometrical representation and characterization of context through semantic spaces; (2) Interferences: the interferences among documents and user’s cognitive status in contextual relevance measurement process; (3) Frameworks: general frameworks and operational methods for contextual and multimodal IR.

Piwowarski et al. [2] proposed that queries and documents can be modeled as density operators and subspaces respectively, but the tensor space based representation method has not led to a good retrieval performance. The Quantum Language Model (QLM) [4], a more recent QT-based IR model, successfully solved this issue. In QLM, both single terms and compound term dependencies are represented as projectors in a vector space, while queries and documents are represented as density matrices defining a quantum probability distribution in the space. Recently, the intersection between IR and QT has been illustrated in [15]. A document retrieval model based on the notion of signal filtering was proposed in [16].

Quantum theory (e.g., quantum interference) has been regarded as an important feature of the quantum theory and has been applied in quantum cognition and decision making [17,18,19,20,21,22,23,24,25,26]. Khrennikov pointed out that the classical and quantum mechanical models on p-adic information spaces might be able to investigate the flows of information in cognitive and social systems since a p-adic metric gives quite a natural description of the ability to form associations [20]. Khrennikov further studied the information dynamics in cognitive, psychological, social and anomalous phenomena with the quantum or quantum-like probabilistic structure [21,22]. Many quantum based IR research works [6,27], including our approach that incorporates quantum interference in query expansion, are inspired by these fundamental research on quantum cognition [17,18,19,20,21,22,23,24,25,26].

In IR, Zuccon and Azzopardi [6] proposed a Quantum Probability Ranking Principle (QPRP), which advances the traditional Probability ranking principle by considering the inter-document dependency as a kind of quantum interference in the retrieval model. Zhang et al. [27] utilized probabilistic automata and quantum automata to model the cognitive interference in users’ relevance judgements. To our knowledge, little work has been carried out to integrate the quantum interference in query expansion modeling. In this paper, we aim to incorporate the concepts of photon polarization and quantum interference in the development of a novel query expansion model, and apply the model in the session search task.

Recent session search approaches utilize MDP (Markov Decision Process) [28,29] and POMDP (Partially Observable MDP) [30,31] to simulate the session search process and have achieved good search results. However, this existing work is different from ours, in that they made use of pre-defined rules to adjust weights of query terms, while we do not reply on rules and focus on modeling quantum interference in the query expansion model.

3. Background on Photon Polarization with Its Analogy in IR

3.1. Analogy of Photon Polarization in Document Ranking

We first introduce the basic quantum measurement used in the photon polarization experiment. Please refer to [8,9] for the complete description for this experiment. A photon’s polarization state can be modeled by a unit vector pointing to an appropriate direction. Specifically, the quantum state of any arbitrary polarization can be represented by a linear combination $a|\uparrow \rangle +b|\to \rangle$ of two basis vectors $|\uparrow \rangle$ (vertical polarization) and $|\to \rangle$ (horizontal polarization), where the amplitudes a and b are complex numbers such that ${\left|a\right|}^2+{\left|b\right|}^2=1$. The quantum measurement on a state transforms the state into one of the measuring device’s associated orthonormal basis. The probability that the state is measured by a basis vector is the squared magnitude of the amplitude in the direction of the corresponding basis vector. For example, a state $\phi =a|\uparrow \rangle +b|\to \rangle$ is measured by $|\uparrow \rangle$ with probability ${\left|a\right|}^2$, and by $|\to \rangle$ with probability ${\left|b\right|}^2$. After the measurement of $|\uparrow \rangle$, the state $\phi$ will collapse to $a|\uparrow \rangle$. Similarly, after the measurement of $|\to \rangle$, $\phi$ will collapse to $b|\to \rangle$.

As introduced previously, the photon polarization experiment measures the probability of photons that can pass through a polarization filter. We can draw an analogy of photon polarization in IR. Specifically, as shown in Figure 1 and Figure 2, document collections can be considered as photon sources, and the relevance measurement of documents by a given query can be regarded as the photon polarization filtering. Therefore, we can regard the retrieval process as measuring the probability of each document that can pass through the query’s retrieval filter (as polarization filter). The measured probability can be regarded as the estimated probability of relevance of each document.

Under the Quantum formulation, a document d’s state can be formulated as:

$$|{\phi }_d\rangle =a_d|q\rangle +b_d|\neg q\rangle ,$$

(1)

where q is the original query, $|q\rangle$ denotes the basis vector for relevance, $|\neg q\rangle$ denotes the basis for non-relevance which is orthogonal to $|q\rangle$, and $|a_d{|}^2+{|b_d|}^2=1$. $|a_d{|}^2$ can be estimated by the relevance probability of the document d with respect to q [3].

3.2. Analogy of Photon Polarization in Query Expansion

The photon polarization experiment usually inserts an additional filter between the original filter and the photon receiver (e.g., a screen) (see Figure 3). In information retrieval, after the first-round retrieval by the original query q, one can conduct a second-round retrieval by an expanded query $q^e$ [7]. The document d’s state with respect to the expanded query $q^e$ can be represented as

$$|{\phi }_d^e\rangle =a_d^e|q^e\rangle +b_d^e|\neg q^e\rangle ,$$

(2)

where $|a_d^e{|}^2+{|b_d^e|}^2=1$, and $|a_d^e{|}^2$ can be estimated by the relevance probability of document d with respect to $q^e$ [7].

Query expansion has achieved good retrieval performance in ad hoc search scenario [32]. However, the expanded query may shift from the underlying intent of the original query, leading to the query-drift problem [33]. As a result, for some individual queries, the performance of the expanded query can be inferior to that of the original one. To prevent query-drift, the existing fusion models in [33] linearly combine two probabilities $|a_d{|}^2$ and $|a_d^e{|}^2$. Such a direct combination ignores the fact that two probabilities are under different basis, i.e., $|q\rangle$ and $|q^e\rangle$, respectively. For each document d, the relevance probability $|a_d{|}^2$ is calculated by the original query basis $|q\rangle$, while the relevance probability $|a_d^e{|}^2$ is calculated by the expanded query basis $|q^e\rangle$. Theoretically, it could be more reasonable if we can combine the two relevance probabilities in one basis.

Photon polarization provides a new perspective and a novel mathematical framework to look at the query expansion problem (see Figure 3) [7]. According to the quantum measurement introduced in Section 3.1, we can observe in Figure 3 that, after the measurement by the original query q, the document state will collapse to its basis $|q\rangle$. Therefore, after the second measurement, one can compute the probability of the state $|q\rangle$ measured by the expanded query filter basis $|q^e\rangle$. The probability amplitude $a_d^f$ can be represented by the equation:

$$|q\rangle =a_d^f|q^e\rangle +b_d^f|\neg q^e\rangle .$$

(3)

Appendix A.1 shows that in the quantum fusion model (QFM), two complete-form solutions of $a_d^f$ are:

$$\left\{\begin{array}{c}{a}_d^f=a_d{a}_d^e+b_d{b}_d^{e}or\hfill \\ a_d^f=a_d{a}_d^e-b_d{b}_d^e\hfill \end{array}.\right.$$

(4)

Different solutions of $a_d^f$ correspond to different representations of the non-relevance basis (for the expanded query), i.e., $|\neg q^e\rangle$ (see Appendix A.1). In [7], the term $b_d{b}_d^e$ has been omitted in the complete-form solution of $a_d^f$. Then, we can have a simplified solution of $a_d^f$:

$$a_d^f=a_d{a}_d^e.$$

(5)

The squared norm $|a_d^f{|}^2$ is considered as the fused relevance probability in the quantum fusion approach [7]. It is expected that this approach can fuse $|a_d{|}^2$ and $|a_d^e{|}^2$ on the same basis $|q^e\rangle$. In the next section, we will show several limitations of this approach and illustrate the importance of the involvement of the quantum interference in the query expansion approach.

4. An Advanced Quantum-Inspired Query Expansion Approach

In this section, we first show several problems of the above quantum fusion approach. Then, we propose a quantum-inspired query expansion approach to these problems.

4.1. Limitations of Quantum Fusion Model

The complete-form solution of the quantum fusion model was formulated in Equation (4). We will show that this solution of $a_d^f$ in Equation (4) only reflects the measurement of $|q\rangle$ given the basis $|q^e\rangle$ but is actually independent of each document d to some extent. Specifically, based on Equation (3), we can represent $a_d^f$ by an inner-product form $\langle q^e|q\rangle$ as follows:

$$\langle q^e|q\rangle =a_d^f\langle q^e|q^e\rangle +b_d^f\langle q^e|\neg q^e\rangle =a_d^f.$$

(6)

In addition to $a_d^f$, other amplitudes $a_d$ and $a_d^e$ in the quantum fusion solution (see Equation (4)) can also be represented by the inner-product forms $\langle q|{\phi }_d\rangle$ and $\langle q^e|{\phi }_d\rangle$, respectively. In Appendix A.2, we derive the quantum fusion solution using inner-product forms of the amplitudes. Appendix A.2 shows that, although the derivation of $\langle q^e|q\rangle$ has the components $\langle q|{\phi }_d\rangle$ and $\langle q^e|{\phi }_d\rangle$ for each document d (see Equation (A34)), $\langle q^e|q\rangle$ actually just reflects the relations (e.g., Cosine similarity in Equation (A35)) between the original query q and the expanded query $q^e$. In other words, the complete-form solution $a_d^f$ (i.e., $\langle q^e|q\rangle$) of the quantum fusion approach can be considered as a constant value for each document. Therefore, the solution in Equation (4) can not be utilized in a document ranking function.

In the quantum fusion approach, the simplified solution $a_d^f=a_d{a}_d^e$ which omits the $b_d{b}_d^e$ in Equation (4), was used to combine two relevance probabilities and then construct the ranking purpose in [7]. However, the problem is that this simplified approach by multiplying two relevance probabilities together lacks a valid interpretation in a quantum point of view. In other words, if the ranking function is simply $|a_d^f{|}^2=|a_d{|}^2{|a_d^e|}^2$, this combination in a multiplication manner still can not meet a quantum or quantum-like interpretation.

Moreover, after each measurement in Figure 3, the document state will collapse to a certain state (i.e., $|q\rangle$ after the first measurement, and $|q^e\rangle$ after the second measurement). This kind of process does not make use of the quantum uncertainties of the superposition and hardly results in a quantum interference, which will be detailed in Section 4.3.

4.2. A Superposition State of the Document in Information Need Space

Now, we propose a new superposition state of document in the information need space. Instead of the superposition of relevance and non-relevance bases regarding the query q in Equation 1, we will model each document in a superposition of the user’s explicit and implicit information needs. The explicit information need can be represented by the user’s currently input query $q_c$, while the implicit information need can be represented by the hidden query $q_h$. Based on the above ideas, we model each document using the following superposition state:

$$|{\phi }_d\rangle =a_d|q_c\rangle +b_d|q_h\rangle ,$$

(7)

where $|q_c\rangle$ is the basis vector of the current query that the user explicitly input, and $|q_h\rangle$ is the basis vector of the hidden/latent query that the user may be interested in but does not input explicitly. Both the current and hidden queries represent some aspects of the user’s information need. We assume that $|q_c\rangle$ and $|q_h\rangle$ are mutually orthogonal, that is, they represent mutually exclusive events but they are two complementary parts of information need.

The amplitude $a_d$’s squared norm $|a_d{|}^2$ can be estimated by the probability of a document that is relevant to the current query $q_c$, while $|b_d{|}^2$ can be estimated by the probability of a document that is relevant to the hidden query $q_h$. $|a_d{|}^2$ and $|b_d{|}^2$ can be estimated by calculating the relevance score of a document d with respect to the current query terms and the hidden query terms (e.g., historical query terms), respectively. Given a retrieval model, the relevance scores (i.e., $|a_d{|}^2$ and $|b_d{|}^2$) for two basis vectors can be normalized, thus ensuring that $|a_d{|}^2+{|b_d|}^2=1$.

The new document representation in Equation (7) can be more reasonable, compared with the previous representation in Equation (1). In Equation (1), $|\neg q\rangle$ is defined as an abstract non-relevance basis, which is hardly characterized in the real search task. Therefore, the estimation of its amplitude $b_d$ is fully dependent on the estimation for $a_d$ (i.e., $|b_d{|}^2=1-{|a_d|}^2$), where $a_d$ is the amplitude for the input query basis $|q\rangle$. It turns out that only the explicit information need (expressed by the input query q) can influence the relevance measurement and the document ranking. However, in the real search scenario, the implicit/hidden information need in users’ minds also influences the relevance judgement. The advantage of the new representation in Equation (7) is that it actually models both the explicit and implicit information need, in a superposed state.

Before being measured by an expanded query filter, the document state is a superposed state of the explicit and the implicit information need (IN) states modeled in Equation (7), rather than a certain state collapsed to $|q\rangle$ (as discussed in Section 4.1). In other words, one does not know which state (explicit or implicit IN) a document is before it is measured by an expanded query filter. Such an uncertainty encoded in the superposition is the necessary condition of the quantum interference phenomenon [18,19,20,21,22,23,24], which will be detailed next.

4.3. A Quantum Interference Inspired Query Expansion Approach

Recent research in cognitive science [18,19,20,21] addresses that there are some quantum interference phenomena that violate the law of the total probability in decision making. In this paper, we adopt the projection measurement and the path diagram idea in [18], in order to illustrate when the quantum interference can occur in the query expansion scenario. Basically, as aforementioned, before the measurement by the expanded query filter, a superposed state of the document is necessary for the quantum interference. In other words, only if one does not know which path (explicit information need or the implicit information need) that goes to the expanded query filter can the quantum interference occur. Otherwise, the quantum interference can not occur. Next, we explain the cases when the quantum interference can not occur. Note that these cases are corresponding to the quantum fusion model’s idea.

In the condition when the documents sources are measured by the explicit query filter and then the expanded query filter (see Figure 4a), this process follows a certain path ${\phi }_d\mapsto q_c\mapsto q^e$. The probability of the first step ${\phi }_d\mapsto q_c$ is measured as:

$$p({\phi }_d\mapsto q_c)={|\langle q_c|{\phi }_d\rangle |}^2.$$

(8)

The probability of the second step $q_c\mapsto q^e$ is measured as

$$p(q_c\mapsto q^e)={|\langle q^e|q_c\rangle |}^2.$$

(9)

Now, we can get the probability of the whole path ${\phi }_d\mapsto q_c\mapsto q^e$ as

$$\begin{array}{cc}\hfill p({\phi }_d\mapsto q_c\mapsto q^e)=& p({\phi }_d\mapsto q_c)·p(q_c\mapsto q^e),\hfill \\ \hfill =& {|\langle q_c|{\phi }_d\rangle |}^2·{|\langle q^e|q_c\rangle |}^2,\hfill \\ \hfill =& {|\langle q_c|{\phi }_d\rangle \langle q^e|q_c\rangle |}^2.\hfill \end{array}$$

(10)

Similarly, in the condition when the documents sources are measured by the implicit query filter and then the expanded query filter (see Figure 4b), the relevance probability of the document ${\phi }_d$ can be measured as

$$p({\phi }_d\mapsto q_h\mapsto q^e)={|\langle q_h|{\phi }_d\rangle \langle q^e|q_h\rangle |}^2.$$

(11)

It turns out that in this known condition for the document state before being measured by the expanded query filter, the quantum interference can not occur.

On the other hand, before being measured by the expanded query filter, if the document is in a superposed state of the explicit information need basis $|q_c\rangle$ and the implicit information need basis $|q_h\rangle$, the quantum interference can possibly occur since the path from either ${\phi }_d\mapsto q_c\mapsto q^e$ or ${\phi }_d\mapsto q_h\mapsto q^e$ is unknown (see Figure 5). In such an unknown condition, the relevance probability of the document ${\phi }_d$ can be measured as:

$$\begin{array}{cc}\hfill p({\phi }_d\mapsto q^e)=& {|\langle q^e|{\phi }_d\rangle |}^2\hfill \\ \hfill =& {|\langle q_c|{\phi }_d\rangle \langle q^e|q_c\rangle +\langle q_h|{\phi }_d\rangle \langle q^e|q_h\rangle |}^2\hfill \\ \hfill =& (\langle q_c|{\phi }_d\rangle \langle q^e|q_c\rangle +\langle q_h|{\phi }_d\rangle \langle q^e|q_h\rangle )·(\langle q_c|{\phi }_d\rangle \langle q^e|q_c\rangle +\langle q_h|{\phi }_d\rangle \langle q^e|q_h\rangle )†\hfill \\ \hfill =& {|\langle q_c|{\phi }_d\rangle \langle q^e|q_c\rangle |}^2+{|\langle q_h|{\phi }_d\rangle \langle q^e|q_h\rangle |}^2\hfill \\ & +2|\langle q_c|{\phi }_d\rangle \langle q^e|q_c\rangle \langle q_h|{\phi }_d\rangle \langle q^e|q_h\rangle |cos\theta \hfill \end{array},$$

(12)

where the two terms ${|\langle q_c|{\phi }_d\rangle \langle q^e|q_c\rangle |}^2$ and ${|\langle q_h|{\phi }_d\rangle \langle q^e|q_h\rangle |}^2$ correspond to the measured probabilities in Equations (10) and (11), respectively, while the last term (i.e., $2|\langle q_c|{\phi }_d\rangle \langle q^e|q_c\rangle \langle q_h|{\phi }_d\rangle \langle q^e|q_h\rangle |cos\theta$) is called interference term.

Based on Equation (12), we incorporate the quantum interference idea and propose a new query expansion model in session search task which utilizes more search information (e.g., some historical queries and click-through data) than the ad hoc search task described in [7]. Intuitively, a user measures the relevance of a document by both the input query (as the explicit information need) and the hidden query (as the implicit information need in her/his mind). The current query terms reflect the user’s explicit information need and can form the basis vector for $|q_c\rangle$. The historical queries (or clicked documents) can somehow reflect the user’s implicit information need, and the corresponding query terms can form the basis vector for $|q_h\rangle$. Such implicit information in query log is useful to estimate the user’s hidden information need which is not issued in the current query.

In information retrieval, ${|\langle q^e|{\phi }_d\rangle |}^2$ denotes the probability/likelihood of the expanded query $q^e$ given the state ${\phi }_d$ of the document d, which can be regarded as the relevance score of the document d with respect to the expanded query $q^e$. ${|\langle q_c|{\phi }_d\rangle |}^2$ and ${|\langle q_h|{\phi }_d\rangle |}^2$ are estimated by the negative KL-divergence (Kullback–Leibler divergence, as a kind of relevance score equivalent to query likelihood [34]) of $q_c$ and $q_h$, respectively, given the document d). ${|\langle q^e|q_c\rangle |}^2$ and ${|\langle q^e|q_h\rangle |}^2$ can be estimated by the Cosine similarity (as a kind of probability measurement [35]) of the two corresponding basis vectors). The last term (i.e., $2|\langle q_c|{\phi }_d\rangle \langle q^e|q_c\rangle \langle q_h|{\phi }_d\rangle \langle q^e|q_h\rangle |cos\theta$) is the quantum interference term, where θ is an interference parameter.

5. Empirical Evaluation

5.1. Data Set

Our experiments are conducted on the TREC (Text REtrieval Conference) [11] Session tracks 2013 and 2014. There are 87 sessions in Session track 2013 and 1024 sessions in Session track 2014. Since the official assessors only assessed 100 sessions for Session track 2014, we only test the proposed query expansion model on this subset. For each session, there is a current query which is used for the retrieval task. Before the current query, there are a series of interactions, e.g., historical queries and clicks. Session tracks ask us to search documents from a document collection for the current query with the consideration of a series of historical interactions. The document collection is the Clueweb12 (Category B) [12] which contains 52,343,021 webpages crawled from the Internet. The document collections is indexed by the Indri toolkit [36]. In the indexing process, all words are stemmed with Porter’s stemmer and stopwords are removed with the normal English stopword list.

5.2. Experimental Set-Up

5.2.1. Descriptions for Tested Models

As summarized in

Table 1. Summary of all tested models.

Model	Rank Score for Each Document d
LM	$exp\{-KL({\theta }_{q_c},{\theta }_d)\}$
RM	$exp\{-KL({\theta }_{q^e},{\theta }_d)\}$
RM-HS	$exp\{-KL({\theta }_{hs},{\theta }_d)\}$
combMNZ	$({\delta }_q(d)+{\delta }_{q^e}(d))·({\delta }_q(d)|a_d{|}^2+{\delta }_{q^e}(d)|a_d^e{|}^2)$
interpolation	$\lambda {\delta }_q(q)|a_d{|}^2+(1-\lambda ){\delta }_{q^e}(d){|a_d^e|}^2$
QFM1	$({\delta }_q(d)|a_d{|}^2)·({\delta }_{q^e}(d)|a_d^e{|}^2)$
QFM2	$({\delta }_q(d)|a_d{|}^2)·({\delta }_{q^e}(d)|a_d^e{{|}^2)}^{1/\eta }$
QQE	$|a_d{|}^2·s_1+|b_d{|}^2·s_2+2|a_d|·|b_d|\sqrt{s_1·s_2}cos\theta$

, there are eight kinds of methods involved in our experiments. The Language Model (LM) [37] and Relevance-based language Model (RM) [32] are baseline models. In Table 1, ${\theta }_{q_c}$, ${\theta }_{q^e}$ and ${\theta }_d$ are language models for the current query $q_c$, the expanded query $q^e$ and document d, respectively. $KL(·,·)$ is the KL-divergence for two language models. LM is a method for the first-round retrieval using the current query, and RM is a query expansion approach for the second-round retrieval using the expanded query. In order to obtain a baseline that utilizes the session information, we implement a method called RM-HS (i.e., RM with Historical queries and clicked Snippets), in which pseudo feedback documents are replaced by the implicit feedback documents. Each implicit document is a concatenation of historical query terms and clicked snippets for a specific historical interaction.

The experiments also involve four relevance score combination methods for a comparison. They are combMNZ, interpolation, QFM1 and QFM2, described in [7]. The first two methods (i.e., combMNZ and interpolation) linearly combine the two relevance scores $|a_d{|}^2$ and $|a_d^e{|}^2$ in an additive manner, where $|a_d{|}^2$ is the normalized relevance score of LM, and $|a_d^e{|}^2$ is the normalized score of RM. ${\delta }_q(d)$ and ${\delta }_{q^e}(d)$ are two functions, the value of which is 1 if d is in the result list of the corresponding query, and 0 otherwise. The last two methods (QFM1 and QFM2) are the Quantum Fusion Models (QFM), which combine $|a_d{|}^2$ and $|a_d^e{|}^2$ in a multiplicative manner proposed in our previous work [7]. It should be noted that the four score combination methods above have not taken into account the session information, e.g., the historical queries or the click-through data, etc.

The Quantum Query Expansion (QQE) model in Equation (12) is the proposed method in this paper. For QQE, we have implemented four versions according to different estimation methods for $s_1$ and $s_2$ ($s_1={|\langle q^e|q_c\rangle |}^2$ and $s_2={|\langle q^e|q_h\rangle |}^2$, respectively, in Equation (12)) and different acquisition methods for hidden queries $q_h$. For the estimation methods for $s_1$ and $s_2$, one is to use the Cosine similarity between the current query $q_c$ (or the hidden query $q_h$) and expansion query $q^e$; the other one is to tune free parameters $s_1\in [0,1]$ and $s_2=1-s_1$. For the acquisition of hidden queries, we have two methods: (1) the concatenation of historical queries within the current session as hidden queries; (2) the concatenation of all historical queries and clicked snippets as hidden queries. In summary, the proposed model can form four variations denoted by suffix:

• -CH, using Cosine similarity to estimate $s_1$ and $s_2$, and Historical queries as hidden queries.
• -CS, using Cosine similarity to estimate $s_1$ and $s_2$, and historical queries and clicked Snippets as hidden queries.
• -PH, tuning Parameters $s_1$ ($s_2$), and using Historical queries as hidden queries.
• -PS, tuning Parameters $s_1$ ($s_2$), and using historical queries and clicked Snippets as hidden queries.

5.2.2. Evaluation Metrics

We adopt NDCG [38] and ERR [39] as the evaluation metrics. NDCG is defined as $nDCG@n=DCG@n/idealDCG@n$, where DCG (Discount Cumulative Gain) is defined as $DCG@n={\sum }_{i=1}^n(2^{r_i}-1)(log(1+i))$, n is the number of documents in the ranked list, $r_i\in \{0,1,2,3,4\}$ is the relevance degree of document given current query, and $idealDCG@n$ is the maximized $DCG@n$ value.

ERR is short for Expected Reciprocal Rank which is a graded evaluation metric. ERR is defined as $ERR@n={\sum }_{r=1}^n\frac{1}{r}{\prod }_{i=1}^{r-1}(1-R_i)R_r$, where $R_i=(2^{g^i}-1)2^{g_{max}}$, $g^i$ is the relevance degree for $i^{th}$ document, and $g_{max}$ is the max relevance degree.

5.2.3. Parameter Settings

In some of the aforementioned models (e.g., RM, Interpolation, QFM2, and QQE), there are some free parameters, for which the selected values are listed in

Table 2. Parameter settings.

Model	Parameters for TREC 2013	Parameters for TREC 2014
LM	-	-
RM	$fbDoc=10$,$fbTerm=50$	$fbDoc=10$,$fbTerm=50$
RM-HS	$fbTerm=50$, $\lambda =0.7$	$fbTerm=50$, $\lambda =0.7$
combMNZ	-	-
interpolation	$\lambda =0.7$	$\lambda =0.9$
QFM1	-	-
QFM2	$\eta =8.1$	$\eta =8.1$
QQE-CH	$cos\theta =0.25$	$cos\theta =0.25$
QQE-CS	$cos\theta =0.25$	$cos\theta =0.25$
QQE-PH	$s_1=0.13$, $cos\theta =0.25$	$s_1=0.13$, $cos\theta =0.25$
QQE-PS	$s_1=0.19$, $cos\theta =0.25$	$s_1=0.19$, $cos\theta =0.25$

. For RM (a well known pseudo-relevance feedback model), we search $fbDoc\in \{5,10,20,30\}$ (the number of feedback documents) and $fbTerm\in \{10,20,30,50,80,100\}$ (the number of expansion query terms). According to the retrieval performance with respect to $NDCG@10$, we select the optimal parameters $fbDoc$ as $fbDoc=10$ and $fbTerm=50$. For RM-HS, we tune the combination parameter for original query $\lambda \in (0,1)$ with the increment $0.1$. Similarly, for the fusion model "interpolation", we also tune the combination parameter $\lambda \in (0,1)$ with the increment $0.1$, and we finally set $\lambda =0.9$. We set $\eta =8.1$ ($\eta \in [1,10]$). For the proposed models, we regard the interference degree $cos\theta \in [-0.1,0.3]$ as a parameter. The combination parameter $s1\in (0,0.3]$. For more details of the parameter setting, we can refer to Table 2.

5.3. Evaluation Results

In this section, we report and analyze the performance for all tested models on Session Track 2013 and 2014. The evaluation results for all models evaluated with NDCG@10, NDCG@100, ERR@10 and ERR@100 are reported in

Table 3. Evaluation results on Session Track 2013. Significance test has been conducted for all expansion models compared with LM with paired t-test. Symbol ‡ means $p<0.01$, † means $p<0.05$, and boldface means the best performance.

Models	NDCG@10	NDCG@100	ERR@10	ERR@100
LM	0.0552(0.00%)	0.0579(0.00%)	0.0285(0.00%)	0.0356(0.00%)
RM	0.0366(-34.00%)	0.0581(0.35%)	0.0125(-56.00%)	0.0190(-46.63%)
RM-HS	0.0600(9.00%†)	0.0592(2.25%)	0.0280(-2.00%)	0.0349(-1.97%)
combMNZ	0.0514(-7.00%)	0.0546(-5.70%)	0.0263(-8.00%)	0.0334(-6.18%)
Interpolation	0.0497(-10.00%)	0.0566(-2.25%)	0.0250(-12.00%)	0.0352(-1.12%)
QFM1	0.0506(-8.00%)	0.0534(-7.77%)	0.0254(-11.00%)	0.0325(-8.71%)
QFM2	0.0523(-5.00%)	0.0571(-1.38%)	0.0275(-4.00%)	0.0349(-1.97%)
QQE-CH	0.0741(34.00% ‡)	0.0695(20.03% ‡)	0.0374(31.00% ‡)	0.0453(27.25% ‡)
QQE-CS	0.0921(67.00% ‡)	0.0741(27.98% ‡)	0.0564(98.00% ‡)	0.0636(78.65% ‡)
QQE-PH	0.0859(56.00% ‡)	0.0875(51.12% ‡)	0.0439(54.00% ‡)	0.0515(44.66% ‡)
QQE-PS	0.1120(103.00% ‡)	0.0991(71.16% ‡)	0.0689(142.00% ‡)	0.0808(126.97% ‡)

and

Table 4. Evaluation results on Session Track 2014. Significance test has been conducted for all expansion models compared with LM with paired t-test. Symbol ‡ means $p<0.01$, † means $p<0.05$, and boldface means the best performance.

Models	NDCG@10	NDCG@100	ERR@10	ERR@100
LM	0.1445 (0.00%)	0.1185(0.00%)	0.0846 (0.00%)	0.0951(0.00%)
RM	0.1073 (-26.00%)	0.1699(43.38%)	0.0501 (-41.00%)	0.0717(-24.61%)
RM-HS	0.1393 (-4.00%)	0.1105(-6.75%)	0.0844 (0.00%)	0.0946(-0.53%)
combMNZ	0.1421 (-2.00%)	0.1163(-1.86%)	0.0821 (-3.00%)	0.0928(-2.42%)
Interpolation	0.1427 (-1.00%)	0.1173(-1.01%)	0.0826 (-2.00%)	0.0934(-1.79%)
QFM1	0.1415 (-2.00%)	0.1151(-2.87%)	0.0804 (-5.00%)	0.0914(-3.89%)
QFM2	0.1427 (-1.00%)	0.1175(-0.84%)	0.0830 (-2.00%)	0.0937(-1.47%)
QQE-CH	0.1625 (12.00%†)	0.1292(9.03%†)	0.0939 (11.00%†)	0.1043(9.67%†)
QQE-CS	0.1630 (13.00%†)	0.1234(4.14%)	0.0940 (11.00%†)	0.1043(9.67%†)
QQE-PH	0.1824 (26.00% ‡)	0.1824(53.92% ‡)	0.0972 (15.00%†)	0.1105(16.19%†)
QQE-PS	0.1527 (6.00%†)	0.1516(27.93% ‡)	0.0739 (-13.00%)	0.0866(-8.94%)

. LM is the baseline model, which ranks documents with KL based retrieval functions. RM expands the current query by selecting terms from the pseudo-relevance feedback documents (top ranked documents). From the tables, we find that RM fails to outperform the LM consistently across two data sets with respect to all evaluation metrics, which shows that RM is not stable for different search environments. By observing the four fusion based expansion models (e.g., combMNZ, Interpolation, QFM1 and QFM2), we find that the retrieval performances are inferior to the baseline model. The weak performances of the RM and RM-based fusion models demonstrate that the traditional retrieval model may be insufficient for session search task and the hidden information need should be taken into account in the retrieval model. Looking at the RM-HS (i.e., the historical interaction based RM model), we find that it can improve the baseline significantly on Session Track 2013 with respect to NDCG@10, but fails to improve the baseline on Session Track 2014. This shows that the traditional relevance feedback model which has been proven effective in ad hoc retrieval tasks cannot handle complex web search scenarios, e.g., session search.

We then use our proposed interference-based expansion model to integrate historical query terms. The evaluation results in Table 3 and Table 4 show that our expansion models (i.e., “-CH" and “-PH" related QQE models) consistently improve the language model and outperform the other non-QQE query expansion models. After adding the clicked snippets in our models (i.e., “-CS" and “-PS" related QQE models), the performance on TREC 2013 becomes better, which shows that introducing more hidden information can improve the session search performance to some extent.

5.4. Study on the Quantum Interference Term

In this section, we focus on studying the influence of quantum interference on retrieval performance. To this end, we control all free parameters other than $cos\theta$ to report the performance of QQE models. We only report the analysis results with respect to NDCG@10 in Figure 6, since two evaluation metrics (NDCG and ERR) have a similar sensitivity trend in our experiments. In the figure, $cos\theta =0$ means no interference, while $cos\theta >0$ (or $cos\theta <0$) means positive (or negative) interference. The figure shows that the retrieval performance will increase along with the increase of $cos\theta$, which implies that considering positive interference in ranking function can improve the retrieval performance.

6. Conclusions

In this paper, we explore and extend the analogy between Photon Polarization (PP, a typical quantum experiment) and information retrieval (query expansion in particular). The PP inspired Quantum Fusion Model (QFM) only takes into account the input query that can represent the explicit information need. We addressed that, in addition to the explicit information need, the hidden/implicit information need in user’s minds can also influence the relevant judgement. Then, we developed a superposition representation for a document in a two-dimensional (i.e., explicit and implicit) information need space. We analyzed when and why the quantum interference can occur, and postulated the quantum interference if a document is in such a superposed state before the the measurement of the expanded query filter. Based on this postulation, we built a novel Quantum interference based Query Expansion (QQE) model, and implemented this quantum query expansion model in the session search task. Extensive empirical evaluations on Session Tracks 2013 and 2014 showed the effectiveness of the proposed QQE model. Further study on the quantum interference term also demonstrates that introducing quantum interference into the query expansion approach can consistently benefit the retrieval performance in web search scenarios.

In the future, we will further improve the proposed models in the following directions: First, we will investigate different implicit relevance feedback methods for the acquisition of hidden information, e.g., through eye tracking captured words. Second, it is important to model quantum interference to simulate users’ real search process in a principled way. Third, machine learning methods can be introduced into our model to train quantum interference parameters automatically.