Материал: искусственный интеллект

Investigating Bell Inequalities for Multidimensional Relevance Judgments in Information Retrieval

Sagar Uprety1(B), Dimitris Gkoumas1, and Dawei Song1,2

1 The Open University, Milton Keynes, UK

{sagar.uprety,dimitris.gkoumas,dawei.song}@open.ac.uk

2 Beijing Institute of Technology, Beijing, China

Abstract. Relevance judgment in Information Retrieval is influenced by multiple factors. These include not only the topicality of the documents but also other user oriented factors like trust, user interest, etc. Recent works have identified and classified these various factors into seven dimensions of relevance. In a previous work, these relevance dimensions were quantified and user’s cognitive state with respect to a document was represented as a state vector in a Hilbert Space, with each relevance dimension representing a basis. It was observed that relevance dimensions are incompatible in some documents, when making a judgment. Incompatibility being a fundamental feature of Quantum Theory, this motivated us to test the Quantum nature of relevance judgments using Bell type inequalities. However, none of the Bell-type inequalities tested have shown any violation. We discuss our methodology to construct incompatible basis for documents from real world query log data, the experiments to test Bell inequalities on this dataset and possible reasons for the lack of violation.

Keywords: Quantum cognition · Information Retrieval ·

Multidimensional relevance · Bell inequalities

1 Introduction

Information Retrieval (IR) is defined as finding material (documents, videos, audio, etc.) of an unstructured nature that are relevant to an information need of the user. Information Need (IN) of a user is usually expressed as a query. An essential component of IR is the concept of relevance of documents. It is defined as how well a document satisfies the user Information Need. Relevance in IR was traditionally considered to be Topical, i.e. how well the content of the retrieved document matches the topic of the query(e.g. text match). As content similarity matching techniques have become more accurate, almost all of the documents obtained for a query generally satisfy the topicality criteria. Hence users tend to consider other factors while judging documents. These di erent factors have been investigated in several works [3, 20, 21]. In [13], seven relevance

c Springer Nature Switzerland AG 2019

B. Coecke and A. Lambert-Mogiliansky (Eds.): QI 2018, LNCS 11690, pp. 177–188, 2019. https://doi.org/10.1007/978-3-030-35895-2_12

178 S. Uprety et al.

dimensions were identified. Each of these dimensions was quantified by defining certain features, which could be extracted from all query-document pairs. These seven dimensions are described in Table 1.

In [19], a document defined using these relevance dimensions is represented as a two dimensional Hilbert space. Each of the seven relevance dimensions is represented as a basis. The di erent basis correspond to the di erent perspectives of relevance judgment for the same document. Based on which relevance dimension is considered, the same document will have di erent probabilities of relevance. Thus the document exists in multiple states (e.g. highly relevant, not relevant, moderately relevant, etc.) simultaneously and we get a particular judgment depending upon which criteria (relevance dimension) the user used to judge (measure) it. This is analogous to the measurement of electron spin which is either up or down in direction, but depends upon which axis it is measured in. Electrons with spin up along the Z-axis may have both up and down components along the X-axis. So a document may look relevant based on the Topicality dimension, but may not be so along, say, the Reliability dimension. We discuss the methodology used to quantify these seven dimensions and construct Hilbert spaces for documents in the next section.

This incompatibility in judgment perspectives is a fundamental feature of Quantum Mechanics [15]. Incompatibility forbids the possibility of jointly determining the outcome of an event from two perspectives. We investigate whether decision making in IR, consisting of multiple perspectives, has an analogous quantum phenomena. A formal test of quantumness of systems was given in

1964 by Bell [5]. He formulated an inequality which cannot be violated by classical systems governed by joint probability distributions. Quantum Mechanics was shown to violate it for particular settings. In this work, we use another version of the Bell inequality, called the CHSH inequality [10]. The CHSH inequality is given by Eq. (1) for two systems A and B where observables A1 and A2 can be measured in system A and B1 and B2 can be measured in system B. Ai and Bi can take values only in {±1}. It is assumed that the observables have pre-existing values which are not influenced by any other measurement.

The CHSH inequality is violated in Quantum Mechanics using a special composite state of two systems, called the Bell state [14], which has the following form:

where |0 and |1 represent the standard basis for the two systems. Initially, both the systems are in a superposed state. The two outcomes, i.e., corresponding to the |0 and |1 vectors can be obtained with equal probabilities. However, on measuring one system, if one obtains the outcome corresponding to the basis vector |0 , the state of the composite system collapses to |00 . Now it is known for certain that the outcome of the second system also corresponds to |0 . This is true even if the two systems are spatially separated - the measurement on one system reveals the state of the other, instantaneously.

Violation of Bell inequalities by such entangled states prove the impossibility of the existence of a joint probability distribution for the two systems. It rules out the concept of “Local Realism” of the classical world, which is the assumption made while deriving the Bell inequalities. ‘Local’ implies the fact that measurement of one system does not influence that of a spatially separated system. ‘Realism’ assumes that values of physical properties of systems have definite values and exist independent of observation [14].

There have been several works which have investigated violation of Bell inequalities in macroscopic and cognitive systems [1, 2, 6]. This work also investigates the Bell inequalities for violation by user’s composite state for judgment of two documents. After describing the methodology used to quantify the seven relevance dimensions, we describe equivalent Bell inequalities for the user states for documents. Subsequently we give details of the experimental settings used to form the composite system of documents.

2 Quantifying Relevance Dimensions

We represent each document as a two-dimensional real valued Hilbert space. The two basis vectors correspond to relevance and non-relevance of a dimension. For the seven dimensions, we have seven di erent basis in the Hilbert space. The user’s cognitive state for this document is a vector in the Hilbert space,

180 S. Uprety et al.

a superposition of the basis vectors. Using the Dirac notation, we get the user state for a document d in di erent basis as:

and so on, in all seven basis. The coe cients |αx|2 is the weight (i.e., probability of relevance) the user assigns to document d in terms of the dimension x, and

|αx|2 + |βx|2 = 1.

To calculate the coe cients of superposition in a basis, we use the same technique as [?]. The dataset is of query logs from the Bing search engine. Following the methodology in [13], we define a set of features for each of the seven relevance dimensions. For each query-document pair, the set of features for each dimension are extracted and integrated into the LambdaMART [8] Learning to Rank (LTR) algorithm to generate seven relevance scores (one for each dimension) for the query-document pair. Due to lack of space, we refer the readers to [13] for more details on the features defined for each dimension and also how they are used in the LTR algorithm. We thus get seven di erent ranked lists for a query, corresponding to each relevance dimension. Then the scores assigned to a document for each dimension are normalized using the min-max normalization technique, across all the documents for the query. The normalized score for each dimension forms the coe cient of superposition of the relevance vector for the respective dimension. For example, for a query q, let d1, d2, ..., dn be the ranking order corresponding to the “Reliability” dimension, based on the relevance scores of λ1, λ2, ..., λn respectively. We construct the vector for document d1 in

λ1, λ2, ..., λn. Square root is taken to enable calculation of probabilities according to the Born rule. We can thus represent this document in all the seven basis and therefore all the documents in their respective Hilbert spaces.

For documents where α11 and α12 are di erent, we get incompatible basis. Incompatibility in relevance dimensions for judging documents can be manifested in terms of Order E ects. Di erent order of considering relevance dimensions while judging a document will lead to di erent final judgments. As an example,

Fig. 1. Hilbert space representation of Order E ects

Suppose that while judging Document d, the user has the order T opicality → Reliability in mind. Then the final probability of relevance is the projection from

(Fig. 1b).

Order E ects in decision making have been successfully modeled and predicted using the Quantum framework [7, 16].

3 Deriving a Bell Inequality for Documents

3.1CHSH Inequality

In Sect. 2, we showed how we can calculate the relevance probabilities of a document for di erent dimensions. We constructed a Hilbert space for each document, consisting of seven di erent basis, representing each dimension of relevance. Two or more such documents can be considered as a composite system by taking a tensor product of the document Hilbert spaces. If |d1 and |d2 are the state vectors of two documents, we can represent the tensor product as |d1 |d2 . Figure 2 shows the geometrical representation of two such Hilbert spaces. Here

irrelevance in the Habit basis.

In the CHSH inequality, we have observables A1 and A2 for a system taking values in ±1. For a document d1, we have observables corresponding to the di erent relevance dimensions. Taking the case of two relevance dimensions, Habit and Novelty, we have observables Rhab and Rnov which take values in

±1. Where Rhab = +1 corresponds to a projection on the basis vector |R hab,

− |

Rhab = 1 corresponds to the projection on its orthogonal basis vector R hab.